[Swift Algorithm] 불! BOJ #4179

문제 설명

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

 

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

 

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 

 

입출력 예제

입력

4 4
####
#JF#
#..#
#..#

출력

3

 

내 문제 풀이

import Foundation

let size = readLine()!.split(separator: " ").map({Int(String($0))!})
let n = size[0] // 가로 칸 수
let m = size[1] // 세로 칸 수
var maze = [[String]]() // 주어진 미로
var queue_J = [(Int, Int)]() // 지훈이 큐
var queue_F = [(Int, Int)]() // 불 큐
let dx = [-1, 1, 0 , 0], dy = [0, 0, -1, 1] // 상하좌우 검색을 위한 좌표 변화량
var result = 0 // 탈출 시간

func Fire(_ next: inout [(Int, Int)]) {
    // 기존 불 큐에 들어있는 자리들을 모두 검사!
    for i in 0..<queue_F.count {
        let (x, y) = queue_F[i]
        
        for j in 0..<4 {
            let nx = x + dx[j]
            let ny = y + dy[j]
            
            // 미로 범위 안에서 "."을 만난 경우 불이 전파되었음을 "F"로 표시
            if 0 <= nx && 0 <= ny && nx < n && ny < m {
                if maze[nx][ny] == "." {
                    maze[nx][ny] = "F"
                    next.append((nx, ny)) // 파라미터로 받은 빈 배열 next에 전파된 좌표를 하나씩 추가
                }
            }
        }
    }
}

func Jihoon(_ next: inout [(Int, Int)]) -> Bool {
    // 기존 지훈이 큐에 들어있는 자리들을 모두 검사!
    for i in 0..<queue_J.count {
        let (x, y) = queue_J[i]
        
        for j in 0..<4 {
            let nx = x + dx[j]
            let ny = y + dy[j]
            
            // 미로 범위 안에서 "."을 만난 경우 "J"로 표시
            if 0 <= nx && 0 <= ny && nx < n && ny < m {
                if maze[nx][ny] == "." {
                    maze[nx][ny] = "J"
                    next.append((nx,ny)) // 파라미터로 받은 빈 배열 next에 이동한 좌표를 하나씩 추가
                }
            }
            // 검색하는 범위가 미로 밖이라면 지훈이는 탈출에 성공한것,!! 따라서 true 리턴
            else { return true }
        }
    }
    return false
}


// ===== ===== ===== 메인 실행 ===== ===== =====

for _ in 0..<n {
    maze.append(Array(readLine()!).map({String($0)}))
}

for x in 0..<n {
    for y in 0..<m {
        if maze[x][y] == "J" { queue_J.append((x, y)) } // 처음 지훈이의 위치 저장
        else if maze[x][y] == "F" { queue_F.append((x, y)) } // 처음 불의 위치 저장
    }
}

while true {
    // (반복마다 새로운 빈 배열이 필요하므로 여기서 선언)
    var next_J = [(Int, Int)]() // 다음에 탐색할 지훈이의 위치들
    var next_F = [(Int, Int)]() // 다음에 탐색할 불의 위치들
    
    // 더이상 탐색할 지훈이가 없을 때 (전부 이미 불과 만났거나 벽에 부딪혔음)
    if queue_J.isEmpty { print("IMPOSSIBLE"); break }
    
    result += 1 // 지훈이랑 불이 한 번 주변으로 퍼져나갈 때마다 누적되는 값 => 탈출 시간 측정
    
    Fire(&next_F) // 불 퍼져나가는 실행
    
    // 지훈이가 탈출하는 실행으로, 탈출에 성공했을 시(true) result를 출력하고 끝!
    if Jihoon(&next_J) == true { print(result); break }
    
    // 지훈이 이동 큐와 불 이동 큐에 새로 업데이트된 큐 넣어주기
    queue_J = next_J
    queue_F = next_F
}

👉지훈이와 불이 시작하는 위치를 미리 찾고, 각각의 bfs를 따로 돌려야한다는 점이 포인트,!

지훈이가 움직이는 경로를 탐색하는 함수와 불이 움직이는 경로를 탐색하는 함수를 따로 작성하고,
한 번에 움직일 수 있는 만큼씩만 탐색하는 것을 '동시에' 반복하도록 해야한다.

• 우선 지훈이의 자리를 담을 queue_J, 불의 자리를 담을 queue_F를 생성했고
  2중 for문을 이용해 J를 찾으면 queue_J에, F를 찾으면 그 자리를 queue_F에 담았다.
• while문으로 실행을 반복했는데, 반복마다 새로운 위치를 담을 큐 next_J, next_F를 생성했다. 
  1) queue_J가 비게되었다면 더이상 탐색할 지훈이의 자리가 없다는 의미인데,
  이때까지 Jihoon함수의 실행 결과로 인한 실행 종료가 없었던 것이므로
  지훈이는 탈출에 실패했음을 알 수 있다. 따라서 IMPOSSIBLE을 출력해주었다.
  2) 그 외의 경우에는 지훈이가 탈출하는데 걸린 시간을 측정해야하므로 result에 1을 누적했다.
  3) 그리고 Fire, Jihoon함수를 실행시켜서
  현재 각 큐에 담겨있는 자리들이 '한 번씩' 옆으로 퍼져나가는 모든 경우를 고려해주었다.
  Jihoon 함수의 실행 결과가 true라면 탈출에 성공했다는 의미이므로 실행을 종료한다.
  4) 마지막으로 기존 큐를 다음번 반복에서 탐색해야할 자리들로 업데이트해준다.
• Fire이라는 이름의 불의 경로를 탐색하는 bfs함수를 먼저 확인해보자.
  for문을 이용하여 기존 큐에 들어있던 모든 자리를 검사해주었다.
  하위 for문에서 딱 4번 반복을 하여 자리마다 상하좌우로 탐색했는데,
  미로의 범위 안에서 "."을 만났다면 "F"를 저장하여 불이 퍼졌음을 표시했다.
  그리고 inout으로 받은 빈 배열 next에 다음번 함수 실행에서 탐색해야할 자리들을 추가했다.
  => 이 Fire함수는 실행의 결과로 다음에 탐색할 새로운 불 큐를 만들어주는것,!!
• Jihoon이라는 이름의 지훈이의 탈출 경로를 탐색하는 bfs함수를 보자.
  Fire과 같은 로직으로 실행하는데, 하나 다른 점은 Bool 값을 리턴한다는 것.
  새로 탐색할 차례인 자리가 미로의 범위를 넘어선다면, 지훈이가 탈출에 성공했다는 뜻!
  따라서 이 때는 true를 출력해주고, 그 외의 상황은 모두 false를 출력한다.

 

💡 피드백

• 두 개의 bfs를 실행한다고 생각하니까 복잡하게 느껴졌고 그만큼 오래걸린 문제였다.
• 막상 풀고나니까 그냥 진짜 단순하게 bfs 두 개,,!라고 생각하면 편할 것 같고,,
  다만 조금 고려해줘야할 점은 일반적인 bfs 문제들의 경우 하나의 큐를 가지고
  계속 탐색할 자리를 뒤에 추가해가면서 큐가 빌때까지 반복을 수행했다면,
  이 문제는 두 개의 bfs가 동시에 수행되어야하므로 기존의 큐에 바로
  새로운 탐색 자리를 추가하지 않고 새로운 배열에 모아뒀다가,,!
  불과 지훈이 둘다 한 번에 해당하는 이동이 끝나면 그 때 큐를 업데이트하는 것을 반복해야했다.

 

---

 

문제

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