[백준10026] 적록색 약 - 완전탐색, 그래프탐색 (dfs, bfs), 그래프탐색 심화 정리

문제

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

10026번: 적록색약

 

 

문제 분석

시간 복잡도

• N x N 칸 (N: 100)
• 중복 없이 방문: O(N^2)

 

문제 유형

• 완전 탐색
• 인접 4방향 그래프 탐색 (dfs, bfs)

 

설계

dfs, bfs 그래프 탐색의 난이도가 올라갈 수록 "갈 수 있는가?" 조건을 정확히 파악하여 설계하는 것이 중요하다.

(dfs, bfs 설계에 대한 포스팅은 이전 글을 참조)

 

해당 문제의 경우 색약인 사람과 아닌 사람의 "갈 수 있는가?" 조건이 다르다.

공통된 조건은 다음과 같다.

1. 현재 방문한 지점의 색 == 다음 방문할 지점의 색 → 다음 지점으로 방문 가능

 

색약인 사람 추가 조건은 다음과 같다.

1. 현재 방문 색이 빨강이면 다음 방문 색 초록도 방문 가능
2. 현재 방문 색이 초록이면 다음 방문 색이 빨강도 방문 가능

 

dfs 설계

starting point (root): 방문 안한 지점

1. 방문 체크: visited[x][y] = true
2. base case: x
3. recursive case:
   1. 연결된 곳: 4방향
   2. 갈 수 있는가?:
      공통) 배열 안, 방문 안한 곳
      공통) board[x][y] (현재 방문 지점 색) == board[nx][ny] (다음 방문할 지점 색)
      색약 case)
      현재 방문 지점 색 G && 다음 방문 지점 색 R
      현재 방문 지점 색 R && 다음 방문 지점 색 G
4. 방문 체크 해제: x

 

 

코드

public class BOJ10026_적록색약 {
	static int N;
	static char[][] board;
	static boolean[][] visited;
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };

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

		N = Integer.parseInt(br.readLine());
		board = new char[N][N];
		for (int i = 0; i < N; i++) {
			board[i] = br.readLine().toCharArray();
		}

		initializeVisited();
		// 색약x dfs탐색
		int colorWeaknessAreaCount = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j]) {
					colorWeaknessAreaCount++;
					dfs(i, j, false);
				}
			}
		}

		initializeVisited();
		// 색약o dfs 탐색
		int notWeaknessAreaCount = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j]) {
					notWeaknessAreaCount++;
					dfs(i, j, true);
				}
			}
		}

		System.out.println(colorWeaknessAreaCount + " " + notWeaknessAreaCount);

	}

	private static void initializeVisited() {
		visited = new boolean[N][N];
	}

	private static void dfs(int x, int y, boolean colorWeakness) {

		visited[x][y] = true;
		// base case: x

		// recursive case:
		char curColor = board[x][y];
		for (int direct = 0; direct < 4; direct++) {
			int nx = x + dx[direct];
			int ny = y + dy[direct];

			if (isInRange(nx, ny) && !visited[nx][ny]) {
				char nextColor = board[nx][ny];

				if (colorWeakness) {
					if (colorWeaknessCanGo(curColor, nextColor)) {
						dfs(nx, ny, colorWeakness);
					}
				} else {
					if (notWeaknessCanGo(curColor, nextColor)) {
						dfs(nx, ny, colorWeakness);
					}
				}
			}
		}
	}

	private static boolean colorWeaknessCanGo(char curColor, char nextColor) {
		if (curColor == nextColor) {
			return true;
		}
		if (curColor == 'R' && nextColor == 'G') {
			return true;
		}
		if (curColor == 'G' && nextColor == 'R') {
			return true;
		}
		return false;
	}

	private static boolean notWeaknessCanGo(char curColor, char nextColor) {
		if (curColor == nextColor) {
			return true;
		}
		return false;
	}

	private static boolean isInRange(int x, int y) {
		return 0 <= x && x < N && 0 <= y && y < N;
	}
}

 

색약이 아닌 사람에 대한 dfs 탐색 후, visited 배열을 다시 초기화해줌을 주목하자.

색약이 아닌 사람에 대한 dfs 탐색 과정에서 visited 배열에 방문 기록을 해주었으므로 다시 초기화하여 색약인 사람에 대한 dfs 탐색을 진행해야 한다.

 

 

 

결과

 

 

 

기록

• 날짜: 2022-12-26
• 소요시간(dfs): 28분

 

 

 

Remember

dfs, bfs 그래프 탐색의 경우 문제의 난이도가 올라갈 수록 "갈 수 있는가?" 조건이 까다로워진다. 정확히 숙지하여 설계할 것.
ex) https://www.acmicpc.net/problem/23289

23289번: 온풍기 안녕!

해당 문제의 경우 "갈 수 있는가?" 조건이 까다로운 문제로, 벽 유무와 방향에 따라 판단해야 한다.