백준 2234 성곽 Kotlin (dfs, 비트마스킹)

문제 출처 : https://www.acmicpc.net/problem/2234

2234번: 성곽

문제

대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.

1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.

성은 M × N(1 ≤ M, N ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.

출력

첫째 줄에 1의 답을, 둘째 줄에 2의 답을, 셋째 줄에 3의 답을 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 비트마스킹

풀이

그래프 탐색 + 비트마스킹 문제이다.

본인은 dfs로 풀었다.

 

전체적인 풀이는 다음과 같다.

1. 모든 칸을 탐색하며 아직 넘버링 되지 않은 방들을 넘버링한다.

2. 이 과정에서 각 방들의 크기와 방의 개수를 알 수 있고, 각 방들의 크기는 따로 저장하면서 최댓값도 갱신한다.

3. room이라는 방들을 넘버링한 2차원 배열이 완성되면서 문제의 1번, 2번에 대한 답을 구했다.

4. 이제 3번에 대한 답을 구하면 된다.

5. 이전에 저장해놓은 방들을 넘버링한 2차원 배열 room을 모두 탐색하면서, 벽을 하나 허물어서 다른 방과 합쳐질 수
   있다면 그 사이즈의 최댓값을 갱신한다. 

 

방을 넘버링하는 과정에선 벽이 있는 방향은 탐색하지 않기 때문에 그래프의 범위를 벗어날 일이 없지만,

넘버링된 방의 벽을 허물어 합쳐보는 과정에서는 벽이 있는 방향을 탐색하기 때문에 그래프의 범위를 벗어나는 경우를 생각해야 한다.

bfs 풀이도 별 다를 게 없다.

핵심은 벽이 있는지 없는지 찾아내는 것인데, 문제에 힌트로 나왔듯 비트마스킹으로 하면 된다.

for(i in 0 until 4){

(1 shl i) // 1,2,4, 8

}

그냥 배열에 1,2,4,8 넣어놔도 된다.

코드

val dirXY = arrayOf(arrayOf(0,1),arrayOf(0,-1),arrayOf(1,0),arrayOf(-1,0))
val dir = arrayOf(4,1,8,2)
val br = System.`in`.bufferedReader()
var roomCnt=0
var maxSize=1
var curSize=0
var maxDeleteWallSize=0
fun dfs(r : Int, c : Int, num : Int, graph : Array<List<Int>>, room : Array<IntArray>){
    room[r][c]=num
    curSize++
    for(i in 0 until 4){
        //해당 방향에 벽이 없으면 ㄱ
        if(graph[r][c] and dir[i] ==0){
            var nr = r + dirXY[i][0]
            var nc = c + dirXY[i][1]
            //이미 방문했다면 스킵
            if(room[nr][nc]!=0) continue
            dfs(nr,nc,num,graph,room)
        }
    }
}

fun main() = with(System.out.bufferedWriter()){
    val (m,n) = br.readLine().split(' ').map{it.toInt()}
    val graph = Array(n){ br.readLine().split(' ').map { it.toInt() } }
    val room = Array(n){IntArray(m)}
    val roomSize = ArrayList<Int>()
    var num=1

    //roomCnt, maxSize구하기, room numbering하기, 각 roomSize 구하기 
    for(r in 0 until n){
        for(c in 0 until m){
            if(room[r][c]==0){
                curSize=0
                dfs(r,c,num++,graph,room)
                roomSize.add(curSize)
                maxSize=  maxSize.coerceAtLeast(curSize)
                roomCnt++
            }
        }
    }

    //maxDeleteWallSize 구하기
    for(r in 0 until n){
        for(c in 0 until m){
            for(i in 0 until 4){
                val nr = r + dirXY[i][0]
                val nc = c + dirXY[i][1]
                //그래프 범위 벗어나는 경우 스킵
                if(nr !in 0 until n || nc !in 0 until m) continue
                //벽이 있으면서 다른 방일 때만
                if(graph[r][c] and dir[i] !=0 && room[r][c] !=room[nr][nc]){
                    maxDeleteWallSize = maxDeleteWallSize.coerceAtLeast(roomSize[room[r][c]-1]+roomSize[room[nr][nc]-1])
                }
            }
        }
    }
    write("$roomCnt\n$maxSize\n$maxDeleteWallSize")
    close()
}