[백준 10026] 적록색약 Java 풀이

접근

구역의 수는 BFS 또는 DFS를 이용하여 구할 수 있습니다. 적록 색약인 사람은 R과 G를 하나의 구역으로 판단하기 때문에 R을 G로 저장하거나 G를 R로 저장하여 적록 색약자가 보는 그림을 갱신한 뒤 구역의 수를 구하면 쉽게 문제를 해결할 수 있습니다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int n;

	// 상, 하, 좌, 우
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 입력 처리
		n = Integer.parseInt(br.readLine());

		int count = 0, weakCount = 0;
		boolean[][] visited = new boolean[n][n];
		boolean[][] weakVisited = new boolean[n][n];
		char[][] painting = new char[n][];
		char[][] weakPainting = new char[n][n];

		for (int i = 0; i < n; i++) {
			painting[i] = br.readLine().toCharArray();
			for (int j = 0; j < n; j++) {
				// 적록 색약자가 보는 그림을 갱신한다.
				weakPainting[i][j] = painting[i][j] == 'R' ? 'G' : painting[i][j];
			}
		}

		// dfs를 이용하여 구분이 가능한 구역의 수를 구한다.
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				// 적록 색약이 아닌 사람
				if (!visited[i][j]) {
					count++;
					visited[i][j] = true;
					dfs(i, j, painting[i][j], visited, painting);
				}
				// 적록 색약인 사람
				if (!weakVisited[i][j]) {
					weakCount++;
					weakVisited[i][j] = true;
					dfs(i, j, weakPainting[i][j], weakVisited, weakPainting);
				}
			}
		}

		// 결과 처리
		System.out.println(count + " " + weakCount);
	}

	static void dfs(int r, int c, char color, boolean[][] visited, char[][] painting) {
		for (int dir = 0; dir < 4; dir++) {
			int nr = r + dr[dir];
			int nc = c + dc[dir];
			if (inRange(nr, nc) && !visited[nr][nc] && painting[nr][nc] == color) {
				visited[nr][nc] = true;
				dfs(nr, nc, color, visited, painting);
			}
		}
	}

	static boolean inRange(int r, int c) {
		return 0 <= r && r < n && 0 <= c && c < n;
	}
}