[백준 10026] 적록색약 (JAVA)

https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

 

이 문제는 적록색약인 사람과 아닌사람이 보는 구간의 개수를 각각 출력해야 하므로

방문 처리할 배열이 2개가 필요하다.

 

그러나 배열만 다르고 실제 수행하는 탐색은 같은 bfs를 사용하므로 객체로 만들어 문제에 접근하도록 하겠다.

 

상하좌우로 인접하며 같은 색깔인 경우에 탐색을 진행하면 되므로 dx, dy 배열

그리고 BFS 알고리즘을 사용할것이므로 큐에대한 자원을 선언해주겠다.

 

	int n,front,rear,size;
	
	int[] dx = { 1 , 0 , -1 , 0 };
	int[] dy = { 0 , 1 , 0 , -1 };
	
	Point[] queue;
	
	void init(int n) {
		this.n = n;
		size = n*n;
		queue = new Point[size];
	}

 

 

BFS 메소드는 현재 색깔과 일치하는지 그리고 탐색을 시작할 좌표에 대한 정보, 그리고 수행할 방문배열에 대해

인자로 받아야한다.

 

	void bfs(int sx, int sy, char c, char[][] metrix) {
		
	}

 

상하좌우를 너비로 해서 인자로 받은 방문배열에 대해 탐색을 수행하는 메소드를 작성한다.

 

인자로 받은 색정보와 일치할 경우만 방문처리후 큐에 삽입하도록하고

방문처리는 RGB와 아예 다른 X문자를 넣어 처리해주었다.

 

	void bfs(int sx, int sy, char c, char[][] metrix) {
		queue[rear++] = new Point(sx,sy);
		metrix[sx][sy] = 'x';
		while(queue[front] != null) {
			Point node = queue[front];
			queue[front++] = null;
			front%=size;
			for(int i = 0; i < 4; i++) {
				int x = node.x + dx[i];
				int y = node.y + dy[i];
				if(x >= 0 && y >= 0 && x < n && y < n && metrix[x][y] == c) {
					queue[rear++] = new Point(x,y);
					rear%=size;
					metrix[x][y] = 'x';
				}
			}
		}
	}

 

 

입력은 배열 2개를 동시에 받도록 했다.

 

이때 적록색맹에 대해 체킹할 배열은 G인 경우만 R로 받도록 해주었다.

 

		for(int i = 0; i < n; i++) {
			String now = in.readLine();
			for(int j = 0; j < n; j++) {
				metrix2[i][j] = metrix1[i][j] = now.charAt(j);
				if(metrix1[i][j] == 'G') {
					metrix2[i][j] = 'R';
				}
			}
		}

 

 

이제 전범위를 순회하며 방문 탐색후 각각 탐색한 횟수를 변수에 저장해주면 된다.

 

		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(metrix1[i][j] != 'x') {
					cnt1++;
					bfs.bfs(i, j, metrix1[i][j], metrix1);
				}
				if(metrix2[i][j] != 'x') {
					cnt2++;
					bfs.bfs(i, j, metrix2[i][j], metrix2);
				}
			}
		}

 

 

예제에 대해 잘 출력 되는것을 확인 할 수 있다.

 

 

 

아래는 코드의 전문이다.

 

package boj3;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Boj10026 {
	
	/*
	 * 제출 完
	 */
	
	int n,front,rear,size;
	
	int[] dx = { 1 , 0 , -1 , 0 };
	int[] dy = { 0 , 1 , 0 , -1 };
	
	Point[] queue;
	
	void init(int n) {
		this.n = n;
		size = n*n;
		queue = new Point[size];
	}
	
	void bfs(int sx, int sy, char c, char[][] metrix) {
		queue[rear++] = new Point(sx,sy);
		metrix[sx][sy] = 'x';
		while(queue[front] != null) {
			Point node = queue[front];
			queue[front++] = null;
			front%=size;
			for(int i = 0; i < 4; i++) {
				int x = node.x + dx[i];
				int y = node.y + dy[i];
				if(x >= 0 && y >= 0 && x < n && y < n && metrix[x][y] == c) {
					queue[rear++] = new Point(x,y);
					rear%=size;
					metrix[x][y] = 'x';
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Boj10026 bfs = new Boj10026();
		
		int n = Integer.parseInt(in.readLine());
		bfs.init(n);
		
		char[][] metrix1 = new char[n][n];
		char[][] metrix2 = new char[n][n];
		
		for(int i = 0; i < n; i++) {
			String now = in.readLine();
			for(int j = 0; j < n; j++) {
				metrix2[i][j] = metrix1[i][j] = now.charAt(j);
				if(metrix1[i][j] == 'G') {
					metrix2[i][j] = 'R';
				}
			}
		}
		
		in.close();
		
		int cnt1 = 0;
		int cnt2 = 0;
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(metrix1[i][j] != 'x') {
					cnt1++;
					bfs.bfs(i, j, metrix1[i][j], metrix1);
				}
				if(metrix2[i][j] != 'x') {
					cnt2++;
					bfs.bfs(i, j, metrix2[i][j], metrix2);
				}
			}
		}
		
		System.out.print(cnt1 + " " + cnt2);
	}

}