[Swift] 백준4179번 불! 문제풀이

코딩테스트를 준비해야하는 시기라서 매일 여러 문제를 풀고 있는데요!

이 문제는 블로그 포스팅해두면 저도 보고 다른 분들도 도움 받을 수 있겠다 생각해서 작성해보려고합니다!

 

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

4179번: 불!

네 이런 문제이구요

BFS로 해결할 수 있는 문제입니다.

지훈이가 탈출할 수 있는 최단시간(경로)을 구하는 문제이니까요!

그런데 여기서 주의할 점은 불의 최단시간(경로)도 구해야한다는 겁니다!

지훈이도 탈출하려할테지만 불도 시간에 따라 번지니까요

이 문제는 BFS 응용 문제 중 시작점이 두가지 종류인 경우를 다루는 유형입니다.

그럼 무엇을 먼저 구해야할까요?

저는 불의 경로를 먼저 구했습니다.

각 좌표마다 불이 갈 수 있는 최단시간을 BFS를 통해 우선 구해두고

지훈이 또한 각 좌표마다 갈 수 있는 최단 시간을 BFS를 통해 구하는 거죠! 대신 여기서 불의 최단시간과 같거나 불이 더 빠른 경우엔 지훈이는 가지 못합니다.

 

시작하기 전 여기서 주의해야할 점이 있습니다.

1. 불은 1곳에서만 난게 아닐 수 있습니다. 여러 곳에서 F가 발견될 수 있어요

2. 지훈이가 바로 탈출하는 경우도 잘 동작해야합니다.

3. 지훈이가 벽에 둘러싸여 있는 경우 고립되어 탈출하지 못하는 경우도 고려해야합니다.

4. 불이 고립되어 퍼지지 않는 경우도 고려해 주어야합니다.

 

여기서 저는 1번 / 4번의 반례를 고려하지 않아서 애먹었었습니다..

 

1번의 경우엔 시작점이 여러개인 BFS를 돌리는 경우 이므로 

불 BFS를 돌릴때 모든 불의 시작점 좌표를 Queue에 넣으면 간단히 해결됩니다.

 

4번의 경우는  아래의 반례가 있는데요!

let (n,m) = (4,4)
var array = [["#","#","#","F"],
             ["#","J",".","#"],
             ["#",".",".","#"],
             ["#",".",".","#"]]

저는 불의 모든 경로에 -1로 초기화 해두었기 때문에 불이 퍼지지 않으면 불의 모든 경로는 -1로 남아있었고

그 결과 지훈이의 BFS를 돌릴 때 모든 좌표에서 불이 그 좌표까지 도착하는 시간이 -1초 이기에 지훈이는 모든 좌표로 이동할 수가 없었습니다.. -1초보다 어떻게 빨리 가겠어요..? 그래서 -1인 경우는 불 안온거니까 이동하라고 추가해주고 해결해줬습니다.

 

여기서 또 하나의 문제 Swift에서 보통 Queue에서 POP을 하신다면 removeFirst()를 쓰실 거에요!

이 removeFirst()는 O(n)의 시간복잡도가 들기때문에 시간초과에러가 납니다!!

이 경우 메모리 효율이 떨어지겠지만! 값을 직접 삭제하지말고 Index를 증가시켜주며 접근하면 시간초과 문제를 해결할 수 있습니다.

 

아래는 통과한 코드를 남기겠습니다.

 

소스 코드

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n,m) = (input[0], input[1])
var array = [[String]]()
for _ in 1...n {
    array.append(readLine()!.map { String($0) })
}

let dx = [0,0,-1,1]
let dy = [1,-1,0,0]

var firePath = Array(repeating: Array(repeating: -1, count: m), count: n)
var jihunPath = Array(repeating: Array(repeating: -1, count: m), count: n)
var jPoint = (0,0)
var max = 0
var fireIdx = 0
var jihunIdx = 0

var isSuccess = false

func bfs() {
    var queue = [(Int, Int)]()
    for i in 0..<n {
        for j in 0..<m {
            if array[i][j] == "F" {
                queue.append((i,j))
                firePath[i][j] = 0
            } else if array[i][j] == "J" {
                jPoint = (i,j)
            }
        }
    }
    
    while fireIdx < queue.count {
        let pop = queue[fireIdx]
        fireIdx+=1
        let (x,y) = (pop.0, pop.1)
        
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx >= 0 && nx < n && ny >= 0 && ny < m && array[nx][ny] != "#" && firePath[nx][ny] == -1 {
                firePath[nx][ny] = firePath[x][y] + 1
                queue.append((nx,ny))
            }
        }
    }
    
    jihunBFS(jPoint.0, jPoint.1)
}

func jihunBFS(_ x: Int, _ y: Int) {
    var queue = [(x, y)]
    jihunPath[x][y] = 0
    
    while jihunIdx < queue.count {
        let pop = queue[jihunIdx]
        jihunIdx += 1
        let (x,y) = (pop.0, pop.1)
        
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx < 0 || nx >= n || ny >= m || ny < 0 {
                isSuccess = true
                max = jihunPath[x][y] + 1
                return
            } else if array[nx][ny] != "#" && jihunPath[nx][ny] == -1 {
                if firePath[nx][ny] == -1 || firePath[nx][ny] > jihunPath[x][y] + 1 {
                    jihunPath[nx][ny] = jihunPath[x][y] + 1
                    queue.append((nx,ny))
                }
            }
        }
    }
}

bfs()

if isSuccess {
    print(max)
} else {
    print("IMPOSSIBLE")
}