[Java] 백준(골드-5) 10026번 - 적록색약
문제 풀이
이 문제는 너비 우선 탐색 BFS를 이용해 풀 수 있는 문제이다.
아이디어 도출
정수를 이용하는 다른 BFS와 달리 문자열을 통해 조건을 부여해야 하는 문제이기에 조건을 잘 선정해야 한다. 필자는 일반적인 사람이 보았을 떄 구역의 개수를 먼저 센 후, 적록색약 사람이 보았을 때 구역의 개수를 세는 순서로 BFS를 이용했다.
또한, 구역의 개수는 BFS 함수의 호출횟수가 된다. 이를 위해 생각한 아이디어는 다음과 같다.
- 입력 배열을 순회하며 R, G, B 구역의 개수를 BFS 탐색으로 센다.
- 적록색약은 R, G를 구분하지 않으니 입력 배열의 G를 R로 변경한다.
- R과 B만 존재하는 배열을 순회하며 R, B 구역의 개수를 BFS 탐색으로 센다.
- 먼저 센 R, G, B 구역의 개수와 이후에 센 R, B 구역의 개수를 저장한 값을 출력한다.
위 아이디어를 위해 이중 for문을 여러개 쓰다보니 시간복잡도 측면에서
O(4n^2)으로 좋지는 못한 것 같다. 개선한다면 BFS 함수에 파라미터를 추가해서 적록색약의 탐색인지, 일반 탐색인지를 추가로 부여해서 하는 방법도 있을 것 같다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
import java.io.*;
import java.util.*;
class Main {
static int[] dx = new int[]{1, 0, -1, 0};
static int[] dy = new int[]{0, 1, 0, -1};
static boolean[][] visited;
static String[][] arr;
static int N;
static int cnt_all;
static int cnt_red_green;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
// 입력 문자열 배열과 방문배열 선언
arr = new String[N][N];
visited = new boolean[N][N];
// 일반 구역 개수와 적녹색약의 구역 개수를 셀 변수 초기화
cnt_all = 0;
cnt_red_green = 0;
// 입력 배열을 채운다.
for(int i=0; i<N; i++) {
String[] input = br.readLine().split("");
for(int j=0; j<N; j++) {
arr[i][j] = input[j];
}
}
// 먼저 R,G,B 구역의 개수를 센다.
// 이떄, R, G, B 구역의 개수는 BFS의 호출횟수가 된다.
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(!visited[i][j]) {
if(arr[i][j].equals("R")) {
BFS(i, j, "R");
cnt_all++;
} else if (arr[i][j].equals("G")){
BFS(i, j, "G");
cnt_all++;
} else if (arr[i][j].equals("B")){
BFS(i, j, "B");
cnt_all++;
}
}
}
}
// 적녹색약 구역의 개수를 세기 위해 방문 배열을 다시 초기화한다.
visited = new boolean[N][N];
// 적녹색약의 구역을 세기 위해 입력배열의 G를 R로 갱신한다.
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(arr[i][j].equals("G")) {
arr[i][j] = "R";
}
}
}
// 마지막으로 R,B 구역의 개수를 센다.
// R, B 구역의 개수는 BFS의 호출횟수가 된다.
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(!visited[i][j]) {
if(arr[i][j].equals("R")) {
BFS(i, j, "R");
cnt_red_green++;
} else if (arr[i][j].equals("B")){
BFS(i, j, "B");
cnt_red_green++;
}
}
}
}
bw.write(cnt_all + " " + cnt_red_green + "\n");
bw.close();
br.close();
}
static void BFS(int x, int y, String color) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x, y});
visited[x][y] = true;
while(!q.isEmpty()) {
int[] now = q.poll();
for(int dir=0; dir<4; dir++) {
int i = now[0] + dx[dir];
int j = now[1] + dy[dir];
if(isRange(i, j)) {
if(!visited[i][j] && arr[i][j].equals(color)) {
visited[i][j] = true;
q.offer(new int[]{i, j});
}
}
}
}
}
static boolean isRange(int x, int y) {
if(0<=x && 0<=y && x<N && y<N) {
return true;
}
return false;
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.