[백준] 10026 (적록색약)

#1 알고리즘

#1-1 탐색 문제

누가봐도 탐색 문제처럼 생겼다. 그렇다면 어떤 탐색을 수행할 것인가?

 

#1-2 탐색 목표

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

나는 위 테스트 케이스에서 각 알파벳 하나씩을 순회하며,

 

11133
22333
33344
33444
44444

∴ 색맹 아닌 기준으로 구역의 수는 총 4개

와 같은 식으로 변경할 것이다. '인접한 같은 색'끼리는 같은 숫자를 공유하고, '인접한 다른 색'은 서로 다른 숫자를 지닌다. 이렇게 만들려면, 인접한 다른 색으로 가기 전에 먼저 인접한 같은 색에 서로 같은 숫자를 마킹하는 로직이 필요하다.

 

#1-3 Deque 활용

Double-ended queue - Wikipedia

#1-2에서 말한 로직을 구현하기 위해서 Deque(Double-ended queue)를 활용했다. Deque는 입구가 양 옆으로 뚫린 Queue다. Deque는 그 맨 앞쪽에서 원소를 넣거나, 맨 뒤쪽에서 원소를 넣을 수 있다. 마찬가지로 그 맨 앞쪽에서 원소를 pop하거나, 맨 뒤쪽에서 원소를 pop할 수 있다. 본 게시글에선 Deque 양 끝에서 각각 원소를 넣어줄 것이고, pop은 Deque의 맨 뒤쪽에서만 수행할 것이다.

 

#1-2에서 말한 로직(인접한 다른 색으로 가기 전에 먼저 인접한 같은 색에 서로 같은 숫자를 마킹)를 어떻게 Deque로 구현하는가? 바로, 인접한 다른 색은 Deque의 앞에 넣어주고 인접한 같은 색은 Deque의 뒤에 넣어주는 것이다. pop은 뒤쪽에서만 수행하게 만들 것이므로, 이 Deque는 반드시 인접한 같은 색을 인접한 다른 색보다 먼저 pop하게 된다.

 

#2 여담

문제의 해결 방식 자체는 떠올리기 어렵지 않다. 하지만, 그걸 코드로 구현하는 게 어렵다. 프로그래밍을 하다 보면, 프로그래밍이 마치 글쓰기와 비슷하다는 생각이 들 때가 종종 있다. 키보드로 입력하는 코드가, 물 흐르듯 써지는 글씨와 같았으면 좋겠다.

 

#3 코드 - 코틀린

import java.util.*

var gridCount = -1
lateinit var colors: Array<Array<Char>>
lateinit var colorsForBlind: Array<Array<Char>>

lateinit var numbers: Array<Array<Int>>
val dequeForVisit = ArrayDeque<Array<Int>>()
var areaCount = -1

fun main() {
    // 전역 변수 초기화
    gridCount = readln().toInt()
    colors = Array(gridCount) { Array(gridCount) { ' ' } }
    colorsForBlind = Array(gridCount) { Array(gridCount) { ' ' } }
    numbers = Array(gridCount) { Array(gridCount) { -1 } }

    // 입력으로부터, 배열 'colors' 및 'colorsForBlind' 완성
    for (i: Int in 0..<gridCount) {
        val row = readln()
        for (j: Int in row.indices) {
            val color = row[j]
            colors[i][j] = color
            colorsForBlind[i][j] = if (color == 'G') {
                'R'
            } else {
                color
            }
        }
    }

    // 배열 'numbers' 완성 및 영역 갯수 return
    traversal()
    val areaCount1 = areaCount
    numbers = Array(gridCount) { Array(gridCount) { -1 } } // 재사용을 위한 초기화

    // 배열 'numbers' 재완성 및 영역 갯수 return
    traversalForBlindness()
    val areaCount2 = areaCount

    println("$areaCount1 $areaCount2")
}

fun traversal() {
    dequeForVisit.addFirst(arrayOf(-1, -1, 0, 0))
    while (dequeForVisit.isNotEmpty()) {
        visit(colors, dequeForVisit.removeLast())
    }
}

fun traversalForBlindness() {
    dequeForVisit.addFirst(arrayOf(-1, -1, 0, 0))
    while (dequeForVisit.isNotEmpty()) {
        visit(colorsForBlind, dequeForVisit.removeLast())
    }
}

fun visit(colors: Array<Array<Char>>, visitInfo: Array<Int>) {
    val prevY = visitInfo[0]
    val prevX = visitInfo[1]
    val y = visitInfo[2]
    val x = visitInfo[3]

    if (isCalculated(y, x)) {
        return
    }

    // numbers[y][x]에 들어갈 값 계산, 대입
    if (prevY == -1) {
        areaCount = 1
        numbers[y][x] = areaCount
    } else {
        numbers[y][x] = if (colors[prevY][prevX] == colors[y][x]) {
            areaCount
        } else {
            ++areaCount
        }
    }

    // 다음 순회 준비
    for (next in getNexts(y, x)) {
        val nextY = next.first
        val nextX = next.second

        if (colors[y][x] == colors[nextY][nextX]) {
            dequeForVisit.addLast(arrayOf(y, x, nextY, nextX))
        } else {
            dequeForVisit.addFirst(arrayOf(y, x, nextY, nextX))
        }
    }
}

fun getNexts(y: Int, x: Int): ArrayList<Pair<Int, Int>> {
    val nexts = ArrayList<Pair<Int, Int>>()

    // 동 (x + 1)
    if (isMovable(y, x + 1)) {
        nexts.add(Pair(y, x + 1))
    }
    // 서 (x - 1)
    if (isMovable(y, x - 1)) {
        nexts.add(Pair(y, x - 1))
    }
    // 남 (y + 1) y축은 x축과 달리 내림차순으로 입력되었으므로 남쪽은 (y - 1)이 아니라 (y + 1)다.
    if (isMovable(y + 1, x)) {
        nexts.add(Pair(y + 1, x))
    }
    // 북 (y - 1)
    if (isMovable(y - 1, x)) {
        nexts.add(Pair(y - 1, x))
    }

    return nexts
}

fun isMovable(y: Int, x: Int): Boolean {
    // y축으로 영역을 벗어나거나, x축으로 영역으로 벗어나지 '않는다면'(!)
    return !(y !in 0..<gridCount || x !in 0..<gridCount)
}

fun isCalculated(y: Int, x: Int): Boolean {
    return numbers[y][x] != -1
}