적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
일단 DFS 자체를 연습하기 위해 처음엔 문제의 조건 (색약) 을 생각하지 않고 그냥 DFS 완전 탐색으로 일단 풀어보았다.
여태 카카오 문제를 많이 풀어보면서 완전 탐색문제의 풀이를 찾아보면 대부분이 DFS 는 재귀로 푸는 것을 보았다.(이유는 모르겠다.)
그래서 재귀로 구현한 DFS 를 작성했다.
- 모든 노드에 대해 반복을 진행하여 해당 노드가 방문하지 않은 노드라면 탐색을 진행하고, 카운트 값을 증가 시킨다.
- 탐색은, 자신과 같은 색이라면 방문 후 방문체크를 수행한다.
- 위의 알고리즘을 진행하면 서로 다른 색을 방문했을 때 카운트 값을 증가시키기 때문에 서로 다른 색의 구역을 구하는 값과 같아진다.
그 다음은 같은 값을 BFS 로도 구할 수 있기 때문에 문제에 주어진 조건, 색약의 경우 R=G 를 같은 값으로 보기 때문에 해당 조건을 추가해준 탐색은 BFS 로 구현했다.
- 모든 노드에 대해 반복을 진행하여 해당 노드가 방문하지 않은 노드라면 탐색을 진행하고, 카운트 값을 증가 시킨다.
- 탐색은
- R, G 의 경우 4방 (상, 하, 좌, 우) 의 값이 B 가 아니면 방문
- B 의 경우 4방 (상, 하, 좌, 우) 의 값이 B 라면 방문
import java.util.*
val dx = intArrayOf(0, 1, 0 ,-1)
val dy = intArrayOf(1, 0, -1, 0)
fun main(args: Array<String>) {
/*
5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
*/
val N = readLine()!!.toInt()
val graph = Array(N+2) { Array(N+2) {'N'} }
val visit = Array(N+2) { BooleanArray(N+2) {false} }
val visit2 = Array(N+2) { BooleanArray(N+2) {false} }
var count = 0
for (i in 1..N) {
val temp = readLine()!!
for (j in 1..N) {
graph[i][j] = temp[j-1]
}
}
for (i in 1..N) {
for (j in 1..N) {
if (!visit[i][j]) {
dfs(i, j, N, graph, visit)
count++
}
}
}
print("$count ")
count = 0
for (i in 1..N) {
for (j in 1..N) {
if (!visit2[i][j]) {
bfs(i, j, N, graph, visit2)
count++
}
}
}
print(count)
}
fun dfs(x: Int, y: Int, n: Int, graph: Array<Array<Char>>, visit: Array<BooleanArray>) {
visit[x][y] = true
for (i in 0 until 4) {
val nx = x + dx[i]
val ny = y + dy[i]
if (graph[nx][ny] == 'N') continue
if (!visit[nx][ny] && graph[nx][ny] == graph[x][y]) {
dfs(nx, ny, n, graph, visit)
}
}
}
fun bfs(x: Int, y: Int, n:Int, graph: Array<Array<Char>>, visit2: Array<BooleanArray>) {
val queue: Queue<Pair<Int, Int>> = LinkedList()
queue.offer(Pair(x, y))
visit2[x][y] = true
while (queue.isNotEmpty()) {
val now = queue.poll()
for (i in 0 until 4) {
val nx = now.first + dx[i]
val ny = now.second + dy[i]
if (graph[nx][ny] == 'N') continue
when (graph[now.first][now.second]) {
'B' -> {
if (graph[nx][ny] == 'B' && !visit2[nx][ny]) {
queue.offer(Pair(nx, ny))
visit2[nx][ny] = true
}
}
else -> {
if (graph[nx][ny] != 'B' && !visit2[nx][ny]) {
queue.offer(Pair(nx, ny))
visit2[nx][ny] = true
}
}
}
}
}
}
DFS 혹은 BFS 를 수행할 때, 방문 체크용 배열이나 그래프 같은 경우는 전역 변수로 선언하면 굳이 함수에 인자로 넘겨주지 않아도 될 것 같다.
(문제의 조건마다 다르겠지만 일반적으로)
툭 건들면 나올 수 있을만큼 코드로 바로 작성할 수 있게 연습이 필요하다는 것을 느꼈다.