[백준 2234번] [Kotlin] 성곽

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

2234번: 성곽

 

난이도 : 골드 3
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 비트마스킹

 

 

접근법

 

DFS / BFS를 이용한 그룹화 문제입니다.

특이한 점은 0 ~ 15 범위 내 숫자가 주어져 벽의 위치를 알려준다는 점인데요.

 

서쪽에 벽이 있을 때는 1을,

북쪽에 벽이 있을 때는 2를,

동쪽에 벽이 있을 때는 4를,

남쪽에 벽이 있을 때는 8을 더한 값이 주어집니다.

 

예를 들어 (0, 0)의 경우 북, 서, 남 세 방향에 있으므로 1 + 2 + 8 = 11이 주어집니다.

하지만 11을 1 + 2 + 8로 분해하기는 조금 번거로울 것 같은데요.

 

 

2진수 비트로 생각해보기

각 수를 이진수의 비트로 생각해봅시다.

1은 0001,

2는 0010,

4는 0100,

8은 1000 으로 나타낼 수 있습니다.

11의 경우 1011로 나타낼 수 있으며

8, 2, 1을 의미하는 각 비트가 1로 나타나는 모습입니다.

 

그럼, 비트의 and, or 연산을 떠올려봅시다.

1010

0001을 or(&) 연산하면 어떻게 될까요?

1011이 나옵니다. 두 항중 하나라도 1이라면 1, 둘 다 0일 때에만 0이 됩니다.

 

그렇다면

1011과

1000을 or 연산하면 어떻게 될까요?

1011, 즉 처음 상태 그대로 나옵니다.

 

이 원리를 위 문제에 그대로 적용할 수 있습니다.

 

(0, 0) 칸은 북, 서, 남이 막혀 8 + 2 + 1 = 11로, 1011입니다.

1011과 1000 (8)을 or 연산 해봅시다. 1011로 그대로입니다.

1011과 0100 (4)을 or 연산 해봅시다. 1111로 변화가 생겼습니다.

1011과 0010 (2)을 or 연산 해봅시다. 1011로 그대로입니다.

1011과 0001 (1)을  or 연산 해봅시다. 1011로 그대로입니다.

 

즉, 칸의 숫자와 8, 4, 2, 1을 각각 or 연산해가며,

변화가 생겼다면 해당 숫자가 의미하는 벽이 뚫려있음을, 변화가 없다면 벽이 있음을 알 수 있습니다!!!

 

이제 다음은 DFS / BFS로 그룹화하는 과정이네요.

 

 

 

 

소스코드

전체 소스코드

lateinit var map: Array<List<Int>>
lateinit var visited: Array<IntArray>
var roomSize = 0
var n = 0
var m = 0

fun main() = with(System.`in`.bufferedReader()) {
    val mn = readLine().split(" ").map { it.toInt() }
    m = mn[0]
    n = mn[1]

    visited = Array(n) { IntArray(m) }
    map = Array(n) { readLine().split(" ").map { it.toInt() } }

    var groupIndex = 1
    val groupSizes = ArrayList<Int>().apply { add(0) }

    for (i in 0..<n) {
        for (j in 0..<m) {
            if (visited[i][j] != 0) continue
            roomSize = 0

            dfs(i, j, groupIndex)

            if (roomSize == 0) continue
            groupSizes.add(roomSize)
            groupIndex++
        }
    }

    var maxSizeOfWhenWallBroken = 0

    for (x in 0..<n) {
        for (y in 0..<m) {
            for ((dx, dy) in arrayOf(0 to 1, 1 to 0)) {
                val nx = x + dx
                val ny = y + dy
                if (nx !in 0..<n || ny !in 0..<m || visited[x][y] == visited[nx][ny]) continue
                maxSizeOfWhenWallBroken =
                    maxOf(maxSizeOfWhenWallBroken, groupSizes[visited[x][y]] + groupSizes[visited[nx][ny]])
            }
        }
    }

    println(groupSizes.count() - 1)
    println(groupSizes.max())
    println(maxSizeOfWhenWallBroken)
}

fun dfs(x: Int, y: Int, groupIndex: Int) {
    if (x !in 0..<n || y !in 0..<m || visited[x][y] != 0) return
    visited[x][y] = groupIndex
    roomSize++

    if (map[x][y] or 8 != map[x][y]) dfs(x + 1, y, groupIndex)
    if (map[x][y] or 4 != map[x][y]) dfs(x, y + 1, groupIndex)
    if (map[x][y] or 2 != map[x][y]) dfs(x - 1, y, groupIndex)
    if (map[x][y] or 1 != map[x][y]) dfs(x, y - 1, groupIndex)
}

 

 

 

DFS / BFS를 사용한 그룹화

lateinit var map: Array<List<Int>>
lateinit var visited: Array<IntArray>
var roomSize = 0

====================================================================

fun main() {
	
    var groupIndex = 1
    val groupSizes = ArrayList<Int>().apply { add(0) }
	
    for (i in 0..<n) {
        for (j in 0..<m) {
            if (visited[i][j] != 0) continue
            roomSize = 0

            dfs(i, j, groupIndex)

            if (roomSize == 0) continue
            groupSizes.add(roomSize)
            groupIndex++
        }
    }
}

====================================================================

fun dfs(x: Int, y: Int, groupIndex: Int) {
    if (x !in 0..<n || y !in 0..<m || visited[x][y] != 0) return
    visited[x][y] = groupIndex
    roomSize++

    if (map[x][y] or 8 != map[x][y]) dfs(x + 1, y, groupIndex)
    if (map[x][y] or 4 != map[x][y]) dfs(x, y + 1, groupIndex)
    if (map[x][y] or 2 != map[x][y]) dfs(x - 1, y, groupIndex)
    if (map[x][y] or 1 != map[x][y]) dfs(x, y - 1, groupIndex)
}

 

dfs를 돌 때 마다 방의 크기를 담는 변수인 roomSize를 +1 씩 해줍니다.

 

그리고 visited 배열을 해당 방의 번호로 저장해주는데요.

이는 문제의 3번 조건을 위해 사용됩니다.

 

8, 4, 2, 1과 각각 or 연산을 하며 칸의 번호가 처음 그대로와 같지 않다면,

벽이 없는 것이므로 각각에 맞는 방향으로 재귀적으로 dfs 탐색을 해줍니다.

 

dfs가 끝날 때 마다 방의 크기를 List에 넣어줍니다.

 

 

 

벽을 부셨을 때 방의 최대 크기 구하기

var maxSizeOfWhenWallBroken = 0

for (x in 0..<n) {
    for (y in 0..<m) {
        for ((dx, dy) in arrayOf(0 to 1, 1 to 0)) {
            val nx = x + dx
            val ny = y + dy
            if (nx !in 0..<n || ny !in 0..<m || visited[x][y] == visited[nx][ny]) continue
            maxSizeOfWhenWallBroken =
                maxOf(maxSizeOfWhenWallBroken, groupSizes[visited[x][y]] + groupSizes[visited[nx][ny]])
        }
    }
}

println(groupSizes.count() - 1)
println(groupSizes.max())
println(maxSizeOfWhenWallBroken)

 

 

1번, 2번의 경우 손쉽게 구할 수 있으나,

3번의 경우 다소 고민을 했는데요.

 

위 DFS 과정에서 각 방들과 칸에 번호를 부여하며 탐색했는데요.

그냥 모든 칸에 대해 인접한 칸이 내 칸과 다르다면, 두 방의 사이즈를 더해 벽을 부셨을 때 최댓값을 구할 수 있습니다.

DFS 탐색이 끝날 때 마다 방의 크기를 저장한 것도 이 때문입니다.

 

 

 

후기

DFS/BFS + 비트마스킹 테크닉으로 오랜만에 꽤나 재밌게 푼 문제였습니다.

1, 2번은 꽤나 쉽게 구했지만 3번에서 다소 고민을 했는데,

그냥 인접한 두 칸의 방이 다를 때 더해주면 되는... 아주 간단한 방법으로 구할 수 있었습니다.

너무 어렵게 생각하지 않는 습관을 들여야 할 것 같습니다.

 

물론 어렵게 생각했더니 훨씬 더 어렵게 생각해야 풀 수 있는 문제가 널렸지만요  🤣