[DFS/BFS] 10026. 적록색약

[BOJ] 10026. 적록색약

📌 풀이 과정

1. DFS를 이용한 구역 탐색
   각 구역을 DFS(깊이 우선 탐색) 방식으로 탐색하여 방문한 구역을 체크하고, 새로운 구역을 발견할 때마다 구역 수를 증가시킨다.

2. 맵 변환을 통한 적록색약 시뮬레이션
   적록색약의 경우 'R'과 'G'를 구분하지 못하기 때문에, 맵에서 'G'를 'R'로 변환한다. 이렇게 변환된 맵을 사용하여 적록색약인 경우의 구역 수를 계산한다.

3. 두 번의 구역 수 계산
   첫 번째로 변환하지 않은 원래 맵을 이용해 적록색약이 없는 경우의 구역 수를 계산하고, 두 번째로 변환된 맵을 사용해 적록색약이 있는 경우의 구역 수를 계산한다.

현재 탐색 중인 색과 같은 색인 경우에만 DFS 탐색을 이어가게 되어, 동일한 색깔로 연결된 구역만을 탐색할 수 있도록 구현했다.

✨ 제출 코드

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

public class 적록색약_10026 {

	static int N;
	static char[][] map;
	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()); // 지도의 크기
		map = new char[N][N];
		
		for(int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
		}
		
		System.out.print(countSections() + " "); // 적록색약인 사람이 봤을 때
		convertMap();
		System.out.println(countSections()); // 적록색약이 아닌 사람이 봤을 때
	

	}
	
	private static void convertMap() { // 적록색약인 사람의 경우를 위해 G -> R 맵 변환
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 'G') {
					map[i][j] = 'R';
				}
			}
		}
	}
	
	private static int countSections() {
		int section = 0;
		visited = new boolean[N][N];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(!visited[i][j]) {
					dfs(i, j);
					section++;
				}
			}
		}
		
		return section;
	}
	
	private static void dfs(int x, int y) {}

}

1. dfs(int x, int y, char color)

private static void dfs(int x, int y, char color) {
		visited[x][y] = true;
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny]) continue;
			

			if(map[nx][ny] == color) dfs(nx, ny, color);
		}
	}

2. dfs(int x, int y)

private static void dfs(int x, int y) {
		visited[x][y] = true;
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			if(visited[nx][ny] || map[x][y] != map[nx][ny]) continue;
			

			dfs(nx, ny);
		}
	}