백준 16946 벽 부수고 이동하기 4 Kotlin (bfs)

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

16946번: 벽 부수고 이동하기 4

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

2021.07.07 - [알고리즘 문제 풀이/백준] - 백준 2206 벽 부수고 이동하기 c++ (bfs)

2022.05.25 - [알고리즘 문제 풀이/백준] - 백준 14442 벽 부수고 이동하기 2 Kotlin (bfs)

벽 부수고 이동하기 시리즈~

이 문제도 bfs로 풀면 된다. 물론 dfs로 풀어도 된다.

다만, 시간 복잡도를 줄이기 위해서 약간의 생각이 필요하다.

문제에서 요구하는대로 '1'인 칸에서 이동할 수 있는 칸의 개수를 모두 세어 넣는다고 하면,

'1'은 최대 n*m개로 bfs를 n*m번 돌려야 한다.

bfs의 시간 복잡도는 O(V+E), E는 상수이므로 무시하고 V는 N*M이기 때문에 최종 시간 복잡도는 O(N^2*M^2)

N이 1000, M이 1000이기 때문에 시간 초과다.

 

뭔가 매번 '1'인 칸에서 갈 수 있는 칸들을 세지 않고, 뭔가 미리 갈 수 있는 칸들을 저장해놓는 식으로 최적화할 수 있을 것 같은 느낌!

 

우리가 그래프 문제를 풀 때, 현재 칸과 인접한 칸들을 그룹핑하는 작업을 많이 해봤을 것이다.

이 문제도, '1'이 아닌 '0'(갈 수 있는 칸들)을 먼저 그룹핑하고, 마지막에 '1'이 갈 수 있는 그룹들을 찾아서 그 그룹들의 칸 개수를 더하면 되지 않을까?

 

4 3

101

010

101

000

 

의 예시에서 우선 '0'을 그룹핑해 보자.

1A1

B1C

1D1

DDD

이 경우 

(0,0) 좌표의 '1'은 A그룹의 칸의 개수 +B그룹의 칸의 개수 (이하 '그룹의 칸의 개수'는 생략)

(0,2) 좌표의 '1'은 A+C

(1,1) 좌표의 '1'은 A+B+C+D

(2,0) 좌표의 '1'은 B+D

(2,2) 좌표의 '1'은 C+D

 

아~ 그룹핑 해 놓고 '1'에 대해 인접 4방향만 체크하면 된다.

우리는 각 그룹이 몇 개의 칸을 가지고 있는지를 알아야 되기 때문에,

A = 1

B = 1

C = 1

D = 4

이런 식으로 저장해놓으면 되고, 여기서 ABCD는 1234등의 인덱스라고 생각하면 된다.

 

여기서 주의할 점은, '1'의 인접 4방향 그룹을 더해줄 때, 같은 그룹을 더하는 경우를 방지해야 한다.

000

010

000

의 예에선,

AAA

A1A

AAA

'1'의 4방향을 더하면 A그룹을 4번 더할 수 있기 때문에, 중복 제거도 필수다.

 

첨부터 이 풀이로 바로 풀었으나 시간 초과.

도저히 왜 시간 초과인지 이해가 안 갔었는데, buffer write 대신에 print를 쓰면 시간 초과더라..

 

풀이 요약

1. '0'(갈 수 있는 칸)에 대해 bfs를 돌려 그룹핑하고, 그룹별 칸의 개수를 저장해 놓는다.

2. 모든 '1'(벽)의 인접 4방향을 확인하여 방문할 수 있는 그룹별 칸의 개수를 더해준다. 

 

 

코드

import java.util.*

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

lateinit var graph: Array<IntArray>
val group = Array(1000){IntArray(1000) }
val maxCntInGroup = IntArray(500001)

val dir = arrayOf(
    arrayOf(0,1),
    arrayOf(1,0),
    arrayOf(0,-1),
    arrayOf(-1,0)
)

//0들 그룹핑
fun bfs(r: Int, c: Int, num: Int, n: Int, m: Int) : Int{

    var cnt =1

    group[r][c] = num

    val q: Queue<Pair<Int,Int>> = LinkedList()
    q.add(Pair(r,c))

    while(q.isNotEmpty()){
        val (cr, cc) = q.poll()

        for(i in 0 until 4){
            val nr = cr + dir[i][0]
            val nc = cc + dir[i][1]

            if(nr !in 0 until n || nc !in 0 until m) continue
            if(graph[nr][nc]==1) continue
            if(group[nr][nc]>0) continue

            group[nr][nc] = num
            q.add(Pair(nr,nc))
            cnt++
        }
    }
    return cnt
}

fun main() = with(System.out.bufferedWriter()) {

    //input
    val (n,m) = getIntList()
    graph = Array(n){ br.readLine().map { it.digitToInt() }.toIntArray() }

    //solve
    //그룹별 카운트 세어놓기
    var num=1
    for(r in 0 until n){
        for(c in 0 until m){
            if(graph[r][c]==1) continue
            if(group[r][c] >0) continue
            maxCntInGroup[num] = bfs(r,c,num, n, m)
            num++
        }
    }

    //output
    //인접 4방향의 그룹들의 카운트 +
    for(r in 0 until n){
        for(c in 0 until m){
            if(graph[r][c] != 0){

                //4방향 중복 제거해서 더하기
                var set = mutableSetOf<Int>()
                for (i in 0 until 4) {
                    val nr = r + dir[i][0]
                    val nc = c + dir[i][1]

                    if (nr !in 0 until n || nc !in 0 until m) continue
                    if (graph[nr][nc] == 1) continue
                    if(set.contains(group[nr][nc])) continue
                    set.add(group[nr][nc])
                    graph[r][c] += maxCntInGroup[group[nr][nc]]
                }
                graph[r][c] %= 10
            }
            write("${graph[r][c]}")
        }
        write("\n")
    }
    close()
}