[백준] 10026번: 적록색약
문제
풀이
이 문제는 일반인이 보는 구역과 적록색약이 보는 구역의 개수를 각각 구하는 문제입니다. 문제에서 주어진 색상은 R(빨강), G(초록), B(파랑)이며, 일반인은 세 색을 모두 구분하지만 적록색약은 R과 G를 같은 색으로 인식한다는 점이 핵심입니다. 그래프 탐색 문제로, 각 구역을 DFS또는 BFs로 탐새하며 색이 연결된 구역의 개수를 세면 됩니다. 다만 일반 시야와 적록색약 시야 두 가지 조건에 따라 별도로 탐색을 진행해야 합니다.
접근
먼저 입력받은 색상 정보를 이차원 배열에 저장한 후, 일반인이 보는 시야에서 DFS 탐색을 수행하여 연결된 색상의 구역 수를 셉니다. 그 다음, 적록색약의 시야에서는 R과 G를 동일한 색상으로 처리하기 위해 입력 배열에서 G를 R로 바꾸어 동일한 DFS 알고리즘을 적용합니다. 이처럼 두 번의 DFS 탐색을 통해 일반인과 적록색약의 시야 각각에서의 구역 개수를 계산할 수 있습니다.
코드
import java.util.*;
public class BJ10026 {
static int n;
static char[][] map;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0}; // (1)
static int[] dy = {0, 0, -1, 1}; // (2)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
map = new char[n][n];
for (int i = 0; i < n; i++) {
map[i] = sc.next().toCharArray(); // (3)
}
visited = new boolean[n][n];
int normal = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j]) {
dfs(i, j, map[i][j]); // (4)
normal++;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 'G') map[i][j] = 'R'; // (5)
}
}
visited = new boolean[n][n];
int weak = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j]) {
dfs(i, j, map[i][j]); // (6)
weak++;
}
}
}
System.out.println(normal + " " + weak); // (7)
}
static void dfs(int x, int y, char color) { // (8)
visited[x][y] = true;
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
if (!visited[nx][ny] && map[nx][ny] == color) {
dfs(nx, ny, color); // (9)
}
}
}
}
}
(1), (2) 상하좌우 방향 이동을 위한 델타 배열입니다.
(3) 입력받은 문자열을 한 줄씩 char 배열로 변환하여 map에 저장합니다.
(4) 일반인 기준 DFS 탐색 시작 지점입니다. 연결된 구역을 하나의 영역으로 인식합니다.
(5) 적록색약 처리를 위해 G를 R로 통일합니다.
(6) 적록색약 기준 DFS 탐색 시작 지점입니다.
(7) 일반 시야와 적록색약 시야에서의 구역 수를 출력합니다.
(8) DFS 함수 정의입니다. 현재 위치에서 상하좌우 인접한 같은 색상으로 재귀 탐색을 수행합니다.
(9) 조건을 만족하는 경우 DFS를 재귀 호출하여 연결된 모든 칸을 방문 처리합니다.
결론
이번 문제는 DFS/BFS에 익숙해지기 좋은 그래프 탐색문제였습니다. 조건에 따라 입력값을 적절히 변형한 후 동일한 알고리즘을 적용하는 점이 포인트였습니다. DFS의 활용과 방문 여부를 체크하는 방식, 배열 조작의 중요성을 다시 확인할 수 있었습니다.
어제 25년 1학기 중간고사가 끝나고 오랜만에 백준 문제를 푸니 코드는 꾸준히 짜야된다는 생각이 엄청 많이 들었습니다.. 앞으로는 꾸준하게 열심히 살아보겠습니다~~