[Swift][BFS] 백준 9376번 (탈옥)

요구능력 : 0-1 BFS알고리즘

 

코드설명 : 

 

이 문제는 다익스트라로도 풀린다고 하고 0-1 BFS알고리즘 으로도 문제가 풀린다.

나는 0-1 BFS알고리즘으로 공부하고 여러군데를 참고해서 문제를 풀어봤다.

 

나는 처음에 죄수 2명으로 BFS를 해서 문을 최소로 구하고 탈출시켜봤는데,

예제 입력 5 9에서는 성공했지만

예제 입력 5 11에서는 성공못했다.

답은 0 이지만 내 출력은 1이 나와서인데,

내 출력이 1이 나온이유는 위에 있는 문을 부수면 가장자리(x == 0 or y == 0 or x == h or y == h)로 올경우 종료조건을 줬기 때문이다.

문을 부수더라도 가장최소한으로 움직이는 방법이 되버린것이다.

 

예제 입력 5 11에서 성공하려면 무조건 가장자리에 간다고해서 종료조건이라는걸 만들면 안되겠다.

 

나중에 알고보니 죄수 2명이 아니라 상근이까지 포함해서 움직이는 경우를 알아야 되는것이었다.

문제를 보면 문은 상근이만 열 수 있는것처럼 적혀있는데, 상근이가 감옥문을 최소로 열기위해 혼자서 움직이려면 어떻게든 가능은 할것같은데 반례가 반드시 생길것이다.

 

감옥밖에서 자유롭게 움직인다고 했는데,

그 말은 감옥 겉으로 빈공간이 있다는 것이다.

입력받은 감옥의 크기를 ( h + 2) * (w + 2) 정도로 만들어서 "."으로 둘러쌓아 줘야한다.

그래야 상근이가 위 아래 양옆중 뚫린곳으로 들어 올 수 있다.

 

상근이는 BFS로 모든지점을 돌게될것이다.

모든 지점을 돌면서 우리는 최소한으로 문을 부수고 가는 횟수를 구해야한다.

그런데 만약 일반 BFS를 사용하게 된다면, 아래 그림처럼 queue에 들어가있는 #이 먼저 처리될 경우 문을 부수고 가지 않아도 되서 문을 0번부숴도 도착하는곳을 문을 1번부수고 가는것으로 표시된다.

위와 같은 상황을 없애는게 0-1BFS알고리즘이다.

0-1BFS알고리즘을 사용하면 아래와 같이 가중치가 0인부분을 큐의 맨앞에 집어넣고 먼저 처리해주기 때문에 굳이 벽을 부수지 않아도 되는곳은 부수지않고 이동할 수 있게 된다.

이런식으로 죄수1, 죄수2, 상근이 세명을 각각 BFS로 전부 돌아주면 각자 문을 최소로 부수는 경우로 dist배열을 채울것이다.

 

그럼 이 채워진 배열들을 모두 합쳤을 때 가장 최소값이 나온곳이 문을 최소로 열고 이동할 수 있는 값이다.

이유는 세명이서 문을 각자 따고 만났을 경우에는 밖으로 나갈때는 이미 문이 전부 따여있는 상황이므로 문을 열 필요가 없다.

 

그리고 만약 최소값이 있는곳(세명이서 만난곳)이 #이 있는곳이라면 -2를 해서 result변수에 비교해서 넣어줘야한다.

이유는 셋다 따로 dist배열을 완성했기 때문에 문에서 만나면 문을 딴 횟수가 +2가 되어 있기 때문이다.

 

그리고 나는 60%에서 한번 틀렸는데,

그 이유는 벽이 -1로 도배되어있는걸 생각못하고 최소값을 찾다가 틀린것이다.

벽부분을 제외하려면 아래 코드를 사용하면된다.

if d1[i][j] != -1 && d2[i][j] != -1 && d3[i][j] != -1 {
...}

 

 

 

후기 : 처음접하는건 아닌거같은데 어디서 풀어봣지?

사람세명이 접하는곳이 문을 제일 적게연곳인지는 진짜 생각도못했다..

import Foundation
let testCase = Int(String(readLine()!))!
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]
for _ in 0..<testCase{
    let hw = readLine()!.split(separator: " ").map{Int(String($0))!}
    let h = hw[0]
    let w = hw[1]

    var arr = [[String]]()
    var crimeLoc = [(Int, Int)]()
    for _ in 0..<h{
        arr.append(readLine()!.map{String($0)})
    }
    var map = Array(repeating: Array(repeating: ".", count: w + 2), count: h + 2)
    for i in 0..<h{
        for j in 0..<w{
            map[i + 1][j + 1] = arr[i][j]
            if arr[i][j] == "$"{
                crimeLoc.append((i + 1, j + 1))
                map[i + 1][j + 1] = "."
            }
            
        }
    }
    
    func bfs(_ Loc: (Int, Int)) -> [[Int]]{
        var queue = [(Int, Int)]()
        var dist = Array(repeating: Array(repeating: -1, count: w + 2), count: h + 2)
        queue.append((Loc))
        dist[Loc.0][Loc.1] = 0
        while !queue.isEmpty{
            let pop = queue.removeFirst()
            let x = pop.0
            let y = pop.1
            for i in 0..<4{
                let nx = x + dx[i]
                let ny = y + dy[i]
                if nx < 0 || nx >= h + 2 || ny < 0 || ny >= w + 2 || dist[nx][ny] >= 0{continue}
                if map[nx][ny] == "*" {continue}
                if map[nx][ny] == "#"{
                    dist[nx][ny] = dist[x][y] + 1
                    queue.append((nx, ny))
                }else if map[nx][ny] == "."{
                    dist[nx][ny] = dist[x][y]
                    queue.insert((nx, ny), at: 0)
                }
                
            }
        }
        return dist
    }
    let d1 = bfs(crimeLoc[0])
    let d2 = bfs(crimeLoc[1])
    let d3 = bfs((0, 0))
    var result = Int.max
    for i in 0..<h + 2{
        for j in 0..<w + 2{
            if map[i][j] == "*"{continue}
            if d1[i][j] != -1 && d2[i][j] != -1 && d3[i][j] != -1 {
                var sum = d1[i][j] + d2[i][j] + d3[i][j]
                if map[i][j] == "#"{ sum -= 2}
                result = min(result, sum)
            }
            
        }
    }
    print(result)

}