[백준 10026번] [Kotlin] 적록색약

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

10026번: 적록색약

 

난이도 : 골드 5
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

---

설명

인풋값으로 받는 맵 정보를 두 개의 배열로 받아

적록색약이면 R과 G를 같은 색상으로 판단해 DFS / BFS를 돌리고,

적록색약이 아닌 사람이면 그대로 DFS / BFS를 돌려 풀 수 있는 문제입니다.

 

DFS와 BFS 중 어느 것을 사용해도 무방하나, 본 포스팅에서는 DFS를 사용하였습니다.

 

---

소스코드

val br = BufferedReader(InputStreamReader(System.`in`))
n = br.readLine().toInt()

val map1 = Array(n) { Array(n) { ' ' } }
val map2 = Array(n) { Array(n) { ' ' } }

repeat(n) {
    val string = br.readLine()
    for (i in 0 until n) {
        map1[it][i] = string[i]

        if (string[i] == 'G') map2[it][i] = 'R'
        else map2[it][i] = string[i]
    }
}

 

두 개의 맵 배열을 만들어 적록색약의 경우 R과 G 모두 R로 단일화하여 입력받고,

적록색약이 아닌 경우 그래도 입력받습니다.

 

 

DFS

val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)

fun dfs(x: Int, y: Int, map: Array<Array<Char>>): Boolean {
    if (map[x][y] == ' ')
        return false

    val color = map[x][y]
    map[x][y] = ' '

    for (i in 0 until 4) {
        val nx = x + dx[i]
        val ny = y + dy[i]
        if (nx !in 0 until n || ny !in 0 until n || color != map[nx][ny])
            continue
        dfs(nx, ny, map)
    }

    return true
}

 

맵의 좌표를 방문하였다면 해당 값을 ' '(공백)으로 만들고,

방문한 좌표가 ' '(공백)이면 이미 방문한 것이므로 false를 리턴합니다.

 

 

이후 상하좌우 좌표에 대해 dfs를 수행합니다. 

상하좌우의 xy 좌표가 map의 좌표를 벗어나지는 않는지 검사하고,

해당 좌표의 색상이 현재 좌표의 색상과 같지 않다면 continue를 통해 다음 회차로 넘어갑니다.

 

 

var cnt1 = 0
var cnt2 = 0

repeat(n) { x ->
    repeat(n) { y ->
        if (dfs(x, y, map1)) cnt1++
        if (dfs(x, y, map2)) cnt2++
    }
}

이후, main() 부분에서 전 좌표에 대해 dfs를 수행합니다.

 

이미 방문한 좌표면 ' '(공백)을 만나 false 값을 return 할 것이며,

그렇지 않을 경우 true를 return 하게 됩니다.

 

즉, return 값이 true인 경우만 카운트를 해주면 됩니다.

 

이 문제 같은 경우, 적록색약인 경우와 적록색약이 아닌 경우를 비교하여야 하므로

위에서 각각 생성한 map1, map2를 각각 dfs를 실행시키는 것을 볼 수 있습니다.

 

print("$cnt1 $cnt2")

마지막으로, cnt1과 cnt2를 출력합니다.

 

 

전체 소스코드

import java.io.BufferedReader
import java.io.InputStreamReader

val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)
var n = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    n = br.readLine().toInt()

    val map1 = Array(n) { Array(n) { ' ' } }
    val map2 = Array(n) { Array(n) { ' ' } }

    repeat(n) {
        val string = br.readLine()
        for (i in 0 until n) {
            map1[it][i] = string[i]

            if (string[i] == 'G') map2[it][i] = 'R'
            else map2[it][i] = string[i]
        }
    }

    var cnt1 = 0
    var cnt2 = 0

    repeat(n) { x ->
        repeat(n) { y ->
            if (dfs(x, y, map1)) cnt1++
            if (dfs(x, y, map2)) cnt2++
        }
    }
    print("$cnt1 $cnt2")

}

fun dfs(x: Int, y: Int, map: Array<Array<Char>>): Boolean {
    if (map[x][y] == ' ')
        return false

    val color = map[x][y]
    map[x][y] = ' '

    for (i in 0 until 4) {
        val nx = x + dx[i]
        val ny = y + dy[i]
        if (nx !in 0 until n || ny !in 0 until n || color != map[nx][ny])
            continue
        dfs(nx, ny, map)
    }

    return true
}

 

 

---

후기

 

골드5의 문제이나,

 

앞서 풀이한 같은 그래프 탐색 문제인 전쟁 - 전투 (실버 1) 보다도 체감상 쉽게 느껴졌던 것 같네요.

 

 

뭔가 적록색약인 사람이 바라보는 초록색은 무슨 느낌일까 궁금해졌던 문제였던 것 같습니다.