[10026] 적록색약

---

같은 색으로 이루어져 있는 구역을 구하는 문제이기 때문에 DFS, BFS 로 해결할 수 있다. 

나는 BFS 를 연습하고 있었기 때문에 BFS를 이용해서 문제를 풀었다. 

문자로 입력을 받게 되면 2차원 char 배열을 사용하여야 하고, 계산할때 복잡해 질 것같아서 

R 은 숫자 1 / G 는숫자 2 / B 는 숫자 3 으로 받아 정수 2차원 배열을 구성했다. 

< 문제 해결 과정 >

① 처음에는 적록색약이 아닌 사람이 봤을 때 구역의 수를 구하기 때문에 2차원 배열의 처음부터 끝까지 BFS를 수행해서 영역을 구한다.

② 그리고 적록색약인 사람이 봤을 때 구역의 수를 구할 때에는 visited 배열을 초기화하고, R이 나타내는 1과 G가 나타나는 2가 같기 때문에 다시 배열을 처음부터 끝까지 보면서 숫자 2를 1로 변경하고 BFS를 수행했다.

	import java.util.Scanner;
	import java.util.Queue;
	import java.util.LinkedList;
	// 10026
	public class RedGreen {
	static Queue<Integer> Xqueue;
	static Queue<Integer> Yqueue;
	static boolean[][] visited;
	static int[][] arr;
	static int[][] temp = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
	static int N, cnt;
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	N = sc.nextInt();
	arr = new int[N][N];
	visited = new boolean[N][N];
	for (int i = 0; i < N; i++) {
	String st = sc.next();
	for (int j = 0; j < N; j++) {
	if (st.charAt(j) == 'R')
	arr[i][j] = 1;
	else if (st.charAt(j) == 'G')
	arr[i][j] = 2;
	else
	arr[i][j] = 3;
	}
	}
	// for(int i=0; i<N; i++) {
	// for(int j=0; j<N; j++) {
	// System.out.print(arr[i][j]);
	// }
	// System.out.println();
	// }
	cnt = 0;
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	if (visited[i][j] == false) {
	BFS(i, j);
	cnt++;
	}
	}
	}
	System.out.print(cnt + " ");
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	if (arr[i][j] == 2)
	arr[i][j] = 1;
	}
	}
	visited = new boolean[N][N];
	cnt = 0;
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	if (visited[i][j] == false) {
	BFS(i, j);
	cnt++;
	}
	}
	}
	System.out.print(cnt);
	}
	public static void BFS(int x, int y) {
	Xqueue = new LinkedList<Integer>();
	Yqueue = new LinkedList<Integer>();
	Xqueue.offer(x);
	Yqueue.offer(y);
	visited[x][y] = true;
	while (!Xqueue.isEmpty() && !Yqueue.isEmpty()) {
	int currentX = Xqueue.poll();
	int currentY = Yqueue.poll();
	for (int i = 0; i < 4; i++) {
	int nextX = currentX + temp[i][0];
	int nextY = currentY + temp[i][1];
	if (isInside(nextX, nextY) && visited[nextX][nextY] == false
	&& arr[nextX][nextY] == arr[currentX][currentY]) {
	visited[nextX][nextY] = true;
	Xqueue.offer(nextX);
	Yqueue.offer(nextY);
	}
	}
	}
	}
	public static boolean isInside(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < N)
	return true;
	else
	return false;
	}
	}

view raw RedGreen.java hosted with ❤ by GitHub