BFS 응용문제 풀기

2206. 벽 부수고 이동하기

최단거리 구하는 BFS 문제인데 벽을 하나 부술 수 있다는 조건이 추가되었다

최단 경로로 이동하기 위해 어떤 벽을 부숴야 하는지를 어떻게 구해야 할까 고민됐다

일단 모든 벽을 하나 하나 부쉈을 때 각 최단경로가 어떻게 되는지를 구하는 방법이 생각났는데 시간 초과가 나올 것 같았지만 

생각나는 방법이 없어서 도전해봤더니 역시나 시간초과

변수에 벽을 부쉈는지 여부를 저장하고 이를 확인하여 벽을 부수지 않은 경우 벽을 만나면 부수는 방법도 생각해 봤으나,

0	1 (*)	0
1 (#)	1	0
1	0	0

이런 경우 # 위치의 벽을 부쉈기 때문에 이미 벽을 부쉈다는 체크가 되어있어 * 위치 벽을 부수지 못하고 탈출이 불가능하게 된다

다른 풀이를 봤더니 3차원 배열을 사용하고 있었다 (절대절대 지금 내가 생각할 수 없는 풀이 😓)

visited[x][y][벽을 부쉈는가?] 이런 형태로 모든 경우의 수를 저장할 수 있다

0	1 (*)	0
1 (#)	1	0
1	0	0

0,0 에서는 벽을 부순 적이 없기 때문에 벽을 하나 부술 수 있다 

현 위치(0,0)에 인접한 곳은 *과 #인데 조건 상(벽을 한번도 부순적 없고, 벽이면서 지나지 않은 길) 둘다 부수는 것이 가능하다

벽은 하나만 부술 수 있다 그랬는데 무슨 두 개를 부순다는 거지?

-> 평행세계라고 생각하자 둘은 서로 영향권 밖에 있기 때문에 벽 *이 부숴진 경우와 벽 #이 부숴진 경우가 존재하는 것이다

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

private val dx = arrayOf(1, -1, 0, 0)
private val dy = arrayOf(0, 0, -1, 1)
private lateinit var graph: Array<CharArray>
private lateinit var dist: Array<Array<IntArray>>
private val queue = ArrayDeque<Location>()
private var n = 0
private var m = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    graph = Array(n) { CharArray(m) }
    dist = Array(n) { Array(m) { IntArray(2) { -1 } } }
    // dist[x][y][0] : 벽을 부수지 않고 (x, y)까지 오는데 걸리는 비용
    // dist[x][y][1] : 벽을 부수고 (x, y)까지 오는데 걸리는 비용

    for (i in 0 until n) {
        readLine().forEachIndexed { j, c ->
            graph[i][j] = c
        }
    }

    bw.write("${bfs()}")
    bw.close()
}

private fun bfs(): Int {
    // 초기화 0,0 방문 체크
    dist[0][0][0] = 1
    dist[0][0][1] = 1
    queue.add(Location(0, 0, 0))

    while (queue.isNotEmpty()) {
        val (x, y, isBroken) = queue.remove()
        // 목표 범위 도달
        if (isGoal(x, y))
            return dist[x][y][isBroken]

        val nextDist = dist[x][y][isBroken] + 1

        for (dir in 0 until 4) {
            val nx = x + dx[dir]
            val ny = y + dy[dir]

            if (isOOB(nx, ny)) continue

            // 일반 길 지나기: 지나갈 수 있는 길 + 지난적 없는 길
            if (graph[nx][ny] == '0' && dist[nx][ny][isBroken] == -1) {
                dist[nx][ny][isBroken] = nextDist
                queue.add(Location(nx, ny, isBroken))
            }

            // 벽 부수고 지나기: 벽을 부수지 않았고 + 벽이면서 지나가지 않은 길일 경우
            if (isBroken == 0 && graph[nx][ny] == '1' && dist[nx][ny][1] == -1) {
                dist[nx][ny][1] = nextDist // 벽을 부쉈다고 체크
                queue.add(Location(nx, ny, 1))
            }
        }
    }
    return -1
}

data class Location(val x: Int, val y: Int, val isBroken: Int)

val isOOB = { x: Int, y: Int -> x < 0 || x >= n || y < 0 || y >= m }
val isGoal = { x: Int, y: Int -> x == n - 1 && y == m - 1 }

 

도움된 글

BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS (2022-08-27 업데이트)

방문체크 관련 문제 - 14442 : 벽 부수고 이동하기2, 1175: 배달

 

사실 방문체크에 대해서 완벽하게 이해한건 아니라서 몇개 더 문제를 풀어봐야겠다

확실히 응용문제는 어렵구나 

풀다보면 할 수 있을거야

 

9466. 텀 프로젝트

그래프를 이루지 못하는 원소를 찾는 문제같다

다른 bfs 문제는 갈 수 있는 방향이 상하좌우 네방향이었는데 여기서는 한곳으로만 갈 수 있다 (선택할 수 있는 학생이 한명)

-> 그래프 배우고 다시 풀기

 

2573. 빙산

1. 빙산의 개수를 세고 하나일 경우 2. 빙산 녹이기

var year = 0
var cnt: Int
while (checkIceCount().also { cnt = it } < 2) {
    if (cnt == 0) {
        year = 0
        break
    }

    melt()
    year++
}

어려운건 아닌데 그냥 내가 못풀었다 🫠

1. 빙산 개수 세기

private fun checkIceCount(): Int {
    visited = Array(n) { IntArray(m) { -1 } }

    var count = 0
    for (i in 0 until n) {
        if (count > 1) break
        for (j in 0 until m) {
            if (graph[i][j] == 0 || visited[i][j] != -1) continue

            // bfs
            queue = ArrayDeque<Location>()
            visited[i][j] = 1
            queue.add(Location(i, j))

            while (queue.isNotEmpty()) {
                val (x, y) = queue.remove()

                for (dir in 0 until 4) {
                    val nx = x + dx[dir]
                    val ny = y + dy[dir]

                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue
                    if (graph[nx][ny] == 0 || visited[nx][ny] != -1) continue

                    visited[nx][ny] = 1
                    queue.add(Location(nx, ny))
                }
            }
            count++
        }
    }

    return count
}

2. 빙산 녹이기

빙산을 기준으로 상하좌우 중 몇면이나 바다로 둘러싸여 있는지 확인한다

private fun melt() {
    visited = Array(n) { IntArray(m) { -1 } }

    for (i in 0 until n) {
        for (j in 0 until m) {
            if (graph[i][j] == 0 || visited[i][j] != -1) continue

            // bfs
            val queue = ArrayDeque<Location>()
            visited[i][j] = 1
            queue.add(Location(i, j))

            while (queue.isNotEmpty()) {
                val (x, y) = queue.remove()

                for (dir in 0 until 4) {
                    val nx = x + dx[dir]
                    val ny = y + dy[dir]

                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue
                    if (visited[nx][ny] != -1) continue
                    // 주변이 바다일 경우
                    if (graph[nx][ny] == 0 ) {
                        if (graph[x][y] != 0)
                            graph[x][y]--
                    }
                }
            }
        }
    }
}

 

2146. 다리 만들기

 

13549. 숨바꼭질3

 

1600. 말이 되고픈 원숭이