[Swift] 백준_불!(4179)

문제

 

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

4179번: 불!

 

 

풀이

 

어려웠음.

 

 

불은 사방으로 퍼지고, 사람은 주변으로 한 칸씩 움직일 수 있다.

 

우선, BFS를 이용해 불이 각 칸에 언제 도착하는지 미리 구해놓았따. 이후에, 다시 지훈이에 대해서 BFS를 이용해 각 칸에 도달하는 시간을 계산하였따.

 

이때, fire 배열에서 해당 위치인 [i][j]의 값을 확인해서 person[i][j]보다 값이 작다면 해당 위치는 지훈이가 갈 수 없는 곳이므로 넘겨주었다.

 

이 문제에선 지훈이가 경계를 넘어가야 탈출하는 것이므로 newX나 newY가 경계를 넘어갔다면 무시하는 것이 아닌 반복문을 끝내고 해당 값에 1을 더해서 출력하면된다.

1을 더하는 이유는 break되면 경계면에서 멈추는 것이므로 탈출하기 위해선 한 칸을 더 가야한다. 

이때, check라는 변수를 두어 true로 바꿔주고 반복문이 끝난 뒤에도 check가 false라면 IMPOSSIBLE을 출력하였다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var maze: [[String.Element]] = []
var fire = Array(repeating: Array(repeating: -1, count: input[1]), count: input[0])
var person = Array(repeating: Array(repeating: -1, count: input[1]), count: input[0])
var fireQueue: [[Int]] = []
var personQueue: [[Int]] = []
var idx = 0
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
var minDay = 0
var check = false
for _ in 0..<input[0] {
    maze.append(readLine()!.map { $0 })
}
//초기세팅
for i in 0..<input[0] {
   for j in 0..<input[1] {
       if maze[i][j] == "F" {
           fire[i][j] = 0
           fireQueue.append([i,j])
       }
       if maze[i][j] == "J" {
           person[i][j] = 0
           personQueue.append([i,j])
       }
   }
}
//불이 어느 시간에 도착하는지 먼저 구하기
while idx < fireQueue.count {
    let current = fireQueue[idx]
    idx += 1
    for i in 0..<dx.count {
        let newX = current[0] + dx[i]
        let newY = current[1] + dy[i]
        if newX < 0 || newY < 0 || newX >= input[0] || newY >= input[1] {
            continue
        }
        if fire[newX][newY] == -1 && maze[newX][newY] != "#" {
            fire[newX][newY] = fire[current[0]][current[1]] + 1
            fireQueue.append([newX,newY])
        }
    }
}
idx = 0
//불보다 먼저 도착하는 경우만 생각
outer: while idx < personQueue.count {
    let current = personQueue[idx]
    idx += 1
    for i in 0..<dx.count {
        let newX = current[0] + dx[i]
        let newY = current[1] + dy[i]
        if newX < 0 || newY < 0 || newX >= input[0] || newY >= input[1] {
            //경계를 벗어난 것이므로 탈출한것임.
            check = true
            minDay = person[current[0]][current[1]] + 1
            break outer
        }
        if person[newX][newY] >= 0 || maze[newX][newY] == "#" {
            continue
        }
        if fire[newX][newY] != -1 && fire[newX][newY] <= person[current[0]][current[1]] + 1 {
            continue
        }
        person[newX][newY] = person[current[0]][current[1]] + 1
        personQueue.append([newX, newY])
    }
}
if check {
    print(minDay)
} else {
    print("IMPOSSIBLE")
}

이 풀이가 가능했던 이유는 불과 지훈이가 서로 영향이 없기 때문이다. 단순히 불이 난 곳은 지훈이가 갈 수 없다로만 판단하면 돼서 위와 같은 풀이가 가능하다.

 

_____________________________________________________________________________________________________

 

어려움..