[백준] 2667 - 단지번호붙이기

BFS 를 사용하여 "1" 이 나오는 경우에만 방문하도록 하여 푸는 문제.
연결된 1을 찾아내야하기 때문에 (간선), 격자 자체가 그래프이다.
2차원 배열의 원소 상하좌우를 확인해야하기 때문에 dx dy 값을 주어 풀어야한다.

풀이

private lateinit var houseArr: Array<CharArray>
private lateinit var visitedArr: Array<BooleanArray>
private var apartmentList = mutableListOf<Int>()
private var n = 0

// arr[row][col] 이므로
private val dx = intArrayOf(-1, 1, 0, 0)
private val dy = intArrayOf(0, 0, -1, 1)

fun `2667-단지번호붙이기`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    n = br.readLine().toInt()
    houseArr = Array(n){ br.readLine().toCharArray() }
    visitedArr = Array(n){ BooleanArray(n) }

    for(i in 0 until n){
        for(j in 0 until n){
            /*
            * 집이 존재하지 않거나 이미 방문한 곳이면 넘기기
            * */
            if(houseArr[i][j] == '0' || visitedArr[i][j]) continue

            apartmentList.add(0)
            bfs(i, j)
        }
    }

    apartmentList.sort()

    bw.write("${apartmentList.size}\n${apartmentList.joinToString("\n")}")
    bw.flush()
    bw.close()
    br.close()
}

private fun bfs(startX: Int, startY: Int){
    val arrayDeque = ArrayDeque<Pair<Int, Int>>()

    arrayDeque.add(startX to startY)
    visitedArr[startX][startY] = true

    while (arrayDeque.isNotEmpty()){
        apartmentList[apartmentList.lastIndex]++
        val from = arrayDeque.removeFirst()
        val x = from.first
        val y = from.second

        /*
        * 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 && houseArr[nx][ny] == '1' && !visitedArr[nx][ny]){
                visitedArr[nx][ny] = true
                arrayDeque.addLast(nx to ny)
            }
        }
    }
}

후기

처음에는 격자 자체가 그래프라는 것을 모르고, 2차원 배열을 1차원으로 풀어서 풀었었다.

아래가 코드인데, 이것도 정답이 되긴 하였으나 코드가 길어 2차원 배열로 다시 풀어보았다.
비록 테스트 시간이 1차원배열로 푼게 더 빠르게 나오긴 했지만, 풀이 방식과 실수를 생각한다면 최적의 풀이 방법인 2차원 배열이 더 나아보이긴 한다.

문제를 풀 때 sort() 를 해야한다는 지문을 보지 못하였는데, 맨날 다짐해놓고서 문제 지문을 잘 읽지 못하는 건 어떻게 못하려나 ..

fun main(){ `2667-단지번호붙이기`() }
/*
* 1. 1 부터 n*n 으로 끝나는 IntArray 생성
* 2. 순회하며 자신이 1이고, +1 혹은 +N이 1이면 둘 다 add 하여 인접리스트 생성
* 3. 인접리스트 순회하며 출력 count 증가시키고 단지수만큼 저장.
* */
fun `2667-단지번호붙이기`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val n = br.readLine().toInt()
    var idx = 0
    // 1 - based Index
    val houseArr = IntArray(n * n + 1)
    val adjacencyList = Array(n * n + 1){ mutableListOf<Int>() }
    val visitedArr = BooleanArray(n * n + 1)
    var apartmentIdx = -1
    val apartmentList = mutableListOf<Int>()
    val stringBuilder = StringBuilder()

    repeat(n){
        val charArray = br.readLine().toCharArray()

        for(char in charArray){
            val isExist = char.digitToInt()
            houseArr[++idx] = isExist
        }
    }
    val lastIdx = n * n

    for(i in 1 .. lastIdx){
        if(houseArr[i] == 0) continue

        val nextRow = i + n
        val next = i + 1

        // nextRow 가 n 보다 작아야 nextRow 가 존재함. 이 때, nextRow 가 1이면
        if(nextRow <= lastIdx && houseArr[nextRow] == 1){
            adjacencyList[i].add(nextRow)
            adjacencyList[nextRow].add(i)
        }

        // 끝자리가 아니라면 next 가 존재. 이 때, next 가 1이면
        if(i % n != 0 && houseArr[next] == 1){
            adjacencyList[i].add(next)
            adjacencyList[next].add(i)
        }
    }

    val deque = ArrayDeque<Int>()

    for(i in adjacencyList.indices){
        if(houseArr[i] != 1 || visitedArr[i]) continue

        deque.addLast(i)
        apartmentList.add(1)
        apartmentIdx++
        visitedArr[i] = true

        while (deque.isNotEmpty()){
            val from = deque.removeFirst()

            for(to in adjacencyList[from]){
                if(!visitedArr[to]) {
                    visitedArr[to] = true
                    apartmentList[apartmentIdx]++
                    deque.addLast(to)
                }
            }
        }
    }

    stringBuilder.append("${apartmentList.size}")
    apartmentList.sorted().forEach { stringBuilder.append("\n$it") }

    bw.write(stringBuilder.toString())
    bw.flush()
    bw.close()
    br.close()
}