[백준] 적록 색약

queue에 넣으면서 4개의 경로방향으로 전부 탐색,

전체 경로를 훑으면서 안간곳을 탐색하며 전체 갯수를 구하는데, 모든 반례를 질문게시판에 찾으면서 테스트해도 실패..

 

 

 

 

fun main() = with(Scanner(System.`in`)) {
    val size = nextInt()

    val letterArray = Array(size) { CharArray(size) }
    for (i in 0 until size) {
        letterArray[i] = readln().toCharArray()
    }

    fun bfs(hasRGB: Boolean): Int {
        val queue = LinkedList<Color>()
        val isVisited = Array<Array<Boolean>>(size) { Array(size) { false } }
        val action = arrayOf(Pair(1, 0), Pair(-1, 0), Pair(0, 1), Pair(0, -1))
        var count = 0

        for (i in 0 until size) {
            for (j in 0 until size) {
                if (isVisited[i][j]) {
                    continue
                }
                if (queue.isEmpty()) {
                    count++
                    isVisited[i][j] = true
                    queue.add(
                        Color(
                            x = i,
                            y = j,
                            letter = letterArray[i][j]
                        )
                    )
                }
                while (queue.isNotEmpty()) {
                    val color = queue.poll()
                    for (act in action) {
                        val resultX = color.x + act.first
                        val resultY = color.y + act.second
                        if (resultX < 0 || resultY < 0 || resultX >= size || resultY >= size || isVisited[resultX][resultY]) {
                            continue
                        }
                        if (letterArray[resultX][resultY] == color.letter ||
                            (hasRGB && ((letterArray[resultX][resultY] == 'R' && color.letter == 'G') || (letterArray[resultX][resultY] == 'G' && color.letter == 'R')))
                        ) {
                            isVisited[resultX][resultY] = true
                            queue.add(
                                Color(
                                    x = resultX,
                                    y = resultY,
                                    letter = letterArray[resultX][resultY]
                                )
                            )
                        }
                    }
                }
            }
        }
        return count
    }
    println(bfs(hasRGB = false))
    println(bfs(hasRGB = true))
}


data class Color(val x: Int, val y: Int, val letter: Char)

 

 

아래는 테스트한 케이스들

 

//        val size = 5
//        val letterArray = arrayOf(
//            arrayOf('R', 'R', 'R', 'B', 'B'),
//            arrayOf('G', 'G', 'B', 'B', 'B'),
//            arrayOf('B', 'B', 'B', 'R', 'R'),
//            arrayOf('B', 'B', 'R', 'R', 'R'),
//            arrayOf('R', 'R', 'R', 'R', 'R')
//        )
//        val size = 2
//        val letterArray = arrayOf(
//            arrayOf('G', 'R'),
//            arrayOf('G', 'R'),
//        )

//        val size = 3
//        val letterArray = arrayOf(
//            arrayOf('R', 'R', 'G'),
//            arrayOf('G', 'G', 'R'),
//            arrayOf('G', 'G', 'R')
//        )

//        val size = 2
//        val letterArray = arrayOf(
//            arrayOf('R', 'G'),
//            arrayOf('G', 'R')
//        )

//        val size = 5
//        val letterArray = arrayOf(
//            arrayOf('R', 'R', 'R', 'R', 'R'),
//            arrayOf('R', 'B', 'B', 'B', 'R'),
//            arrayOf('R', 'B', 'G', 'B', 'R'),
//            arrayOf('R', 'B', 'B', 'B', 'R'),
//            arrayOf('R', 'R', 'R', 'R', 'R')
//        )

//        val size = 3
//        val letterArray = arrayOf(
//            arrayOf('G', 'B', 'G'),
//            arrayOf('G', 'B', 'G'),
//            arrayOf('R', 'R', 'R')
//        )

        val size = 20
        val letterArray = arrayOf(
            "BBBBBRRRRRRRRRRRBBBB".toCharArray(),
            "BBBBBRRRRRRRRRRRBBBB".toCharArray(),
            "RBBBBBRRRRRRRRRRBBBB".toCharArray(),
            "RRRBBBBRRRRRRRRRBBBB".toCharArray(),
            "RRRBBBBRRRRRRRRRRBRB".toCharArray(),
            "GRRBBBBRRRRRRRRRRBRR".toCharArray(),
            "GGRRRRBBBRRRRRRRRBBB".toCharArray(),
            "GGGRRRBBBRRRRRRRRBBB".toCharArray(),
            "RRGGGGBBBRRRRRRRRBBB".toCharArray(),
            "BBGGGGBBBBRRRRRRRBBB".toCharArray(),
            "BBGGGGGBBBRRRRRRRBBB".toCharArray(),
            "GBGGGGGBRRRRRRRRRBBB".toCharArray(),
            "GGGGGGGGRRRRRRRRRBBB".toCharArray(),
            "GGGGGGGGGRRRRRRRRBBB".toCharArray(),
            "GGGGGGGGGGRRRRRRRBBB".toCharArray(),
            "RRGGGGGGGGGGRRRRRRBB".toCharArray(),
            "RRGGGGGGGGGGGGGGGRBB".toCharArray(),
            "RRRGGGGGGGGGGGGGGRBB".toCharArray(),
            "GGGGGGGBGGGGGGGGGGBB".toCharArray(),
            "RRRRGGGGGGGGGGGGGGGG".toCharArray()
        )

//        val size = 5
//        val letterArray = arrayOf(
//            arrayOf('R', 'R', 'R', 'B', 'B'),
//            arrayOf('G', 'R', 'B', 'B', 'B'),
//            arrayOf('B', 'B', 'B', 'R', 'R'),
//            arrayOf('B', 'B', 'R', 'R', 'R'),
//            arrayOf('R', 'R', 'R', 'R', 'R')
//        )

//        val size = 5
//        val letterArray = arrayOf(
//            arrayOf('R', 'B', 'R', 'B', 'B'),
//            arrayOf('R', 'R', 'B', 'G', 'G'),
//            arrayOf('B', 'B', 'R', 'B', 'R'),
//            arrayOf('R', 'R', 'R', 'B', 'B'),
//            arrayOf('R', 'R', 'R', 'B', 'R')
//        )

//        val size = 3
//        val letterArray = arrayOf(
//            arrayOf('R', 'B', 'R'),
//            arrayOf('B', 'B', 'B'),
//            arrayOf('R', 'B', 'R'),
//        )