문제 링크 (opens new window)

풀이 (오답)

1. 지훈이 기준으로 BFS 진행
2. BFS 순회 과정에서 가장자리 닿은 경우 visited 좌표값이 최단거리이므로 리턴
3. 지훈이 4방향 이동 후에 불 퍼뜨리기
4. 지훈이의 다음 BFS는 불이 퍼진 뒤에 진행되는 상황

import Foundation

// 가장자리 좌표들 모아두기
// 지훈이 위치부터 가장자리까지 최단거리 계산하기
// 최단거리 중 최솟값 리턴하기

struct Queue<T> {
    var array: [T?] = []
    var head = 0

    var isEmpty: Bool {
        return count == 0
    }

    var count: Int {
        return array.count - head
    }

    mutating func enqueue(_ element: T) {
        array.append(element)
    }

    mutating func dequeue() -> T? {
        guard head < array.count,
              let element = array[head] else { return nil }

        array[head] = nil
        head += 1

        let percentage = Double(head) / Double(array.count)
        if percentage > 0.25 && head >= 50 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

    var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}


let rc = readLine()!.split(separator: " ").map { Int($0)! }; let r = rc[0]; let c = rc[1]
var adj: [[String]] = .init(repeating: [], count: r); var visited: [[Int]] = .init(repeating: .init(repeating: 0, count: c), count: r)
var firePos: [(Int, Int)] = []

var jPos: (Int, Int) = (0,0)
let dy = [-1, 0, 1, 0]; let dx = [0, 1, 0, -1]

for i in 0..<r {
    adj[i] = readLine()!.map { String($0) }
    if let jIndex = adj[i].firstIndex(of: "J") {
        jPos = (i, Int(jIndex))
    }

    for (index, row) in adj[i].enumerated() {
        if row == "F" {
            firePos.append((i, index))
        }
    }
}

func fire() {
    var appendix: [(Int, Int)] = []
    for f in firePos {
        for i in 0..<4 {
            let ny = dy[i] + f.0
            let nx = dx[i] + f.1

            if ny < 0 || nx < 0 || ny >= r || nx >= c || adj[ny][nx] == "#" || adj[ny][nx] == "F" {
                continue
            }
            adj[ny][nx] = "F"
            appendix.append((ny, nx))
        }
    }
    firePos += appendix
}

func bfs(_ here: (Int, Int)) -> Int? {
    visited[here.0][here.1] = 1
    var q = Queue<(Int, Int)>()
    q.enqueue(here)

    while(!q.isEmpty) {
        guard let there = q.dequeue() else { return nil }

        for i in 0..<4 {
            let ny = dy[i] + there.0
            let nx = dx[i] + there.1

            if ny < 0 || nx < 0 || ny >= r || nx >= c || visited[ny][nx] != 0 || adj[ny][nx] == "#" || adj[ny][nx] == "F" {
                continue
            }

            visited[ny][nx] = visited[there.0][there.1] + 1

            if ny == 0 || nx == 0 || ny == r - 1 || nx == c - 1 {
                return visited[ny][nx]
            }
            q.enqueue((ny, nx))
        }
        fire()
    }

    return nil
}

let result = bfs(jPos)
print(result ?? "IMPOSSIPLE")

2차 풀이 (오답)

1. 그래프 뎁스별로 4방향 조회를 모두 진행하고 해당 과정에서 탈출 가능한 경우 최단거리 리턴
2. 뎁스 모두 조회했을때도 여전히 탈출 못했으면 4방향 불지르기

import Foundation

// 가장자리 좌표들 모아두기
// 지훈이 위치부터 가장자리까지 최단거리 계산하기
// 최단거리 중 최솟값 리턴하기

struct Queue<T> {
    var array: [T?] = []
    var head = 0

    var isEmpty: Bool {
        return count == 0
    }

    var count: Int {
        return array.count - head
    }

    mutating func enqueue(_ element: T) {
        array.append(element)
    }

    mutating func dequeue() -> T? {
        guard head < array.count,
              let element = array[head] else { return nil }

        array[head] = nil
        head += 1

        let percentage = Double(head) / Double(array.count)
        if percentage > 0.25 && head >= 50 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

    var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}


let rc = readLine()!.split(separator: " ").map { Int($0)! }; let r = rc[0]; let c = rc[1]
var adj: [[String]] = .init(repeating: [], count: r); var visited: [[Int]] = .init(repeating: .init(repeating: 0, count: c), count: r)
var firePos: [(Int, Int)] = []

var jPos: (Int, Int) = (0,0)
let dy = [-1, 0, 1, 0]; let dx = [0, 1, 0, -1]
var depth = 1; var fireDepth = 0

for i in 0..<r {
    adj[i] = readLine()!.map { String($0) }
    if let jIndex = adj[i].firstIndex(of: "J") {
        jPos = (i, Int(jIndex))
    }

    for (index, row) in adj[i].enumerated() {
        if row == "F" {
            firePos.append((i, index))
        }
    }
}

func fire() {
    var appendix: [(Int, Int)] = []
    for f in firePos {
        for i in 0..<4 {
            let ny = dy[i] + f.0
            let nx = dx[i] + f.1

            if ny < 0 || nx < 0 || ny >= r || nx >= c || adj[ny][nx] == "#" || adj[ny][nx] == "F" {
                continue
            }
            adj[ny][nx] = "F"
            appendix.append((ny, nx))
        }
    }
    firePos += appendix
}

// BFS 뎁스 하나가 끝나고 불질러야됨
func bfs(_ here: (Int, Int)) -> Int? {
    visited[here.0][here.1] = 1
    var q = Queue<(Int, Int)>()
    q.enqueue(here)

    while(!q.isEmpty) {
        guard let there = q.front else { return nil }
        _ = q.dequeue()
//        print()
//        for row in adj {
//            for col in row {
//                print(col, terminator: "")
//            }
//            print()
//        }
        for i in 0..<4 {
            let ny = dy[i] + there.0
            let nx = dx[i] + there.1

            if ny < 0 || nx < 0 || ny >= r || nx >= c || visited[ny][nx] != 0 || adj[ny][nx] == "#" || adj[ny][nx] == "F" {
                continue
            }

            visited[ny][nx] = visited[there.0][there.1] + 1
            adj[ny][nx] = "J"

            depth += 1
            if depth > Int(pow(4.0, Double(fireDepth))) {
                fire()
                fireDepth += 1
            }

            if ny == 0 || nx == 0 || ny == r - 1 || nx == c - 1 {
                return visited[ny][nx]
            }
            q.enqueue((ny, nx))
        }

//        for row in adj {
//            for col in row {
//                print(col, terminator: "")
//            }
//            print()
//        }
    }

    return nil
}

let result = bfs(jPos)
print(result ?? "IMPOSSIPLE")

3차 풀이

1. 지훈이가 현재 위치한 곳까지 (there좌표)의 최단거리 + 1이 불이 there 좌표까지 번지는 데 걸리는 시간보다 적어야함

import Foundation

struct Queue<T> {
    var array: [T?] = []
    var head: Int = 0

    var count: Int {
        return array.count - head
    }

    var isEmpty: Bool {
        return count == 0
    }

    mutating func enqueue(_ element: T) {
        array.append(element)
    }

    mutating func dequeue() -> T? {
        guard head < array.count,
              let element = array[head] else { return nil }

        array[head] = nil
        head += 1

        let percentage = Double(head) / Double(array.count)
        if percentage > 0.25 && array.count > 50 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

    var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}

let rc = readLine()!.split(separator: " ").map { Int($0)! }; let r = rc[0]; let c = rc[1]
var visited: [[Int]] = .init(repeating: .init(repeating: Int.max, count: c), count: r)
var humanVisited: [[Int]] = .init(repeating: .init(repeating: 0, count: c), count: r)
var adj: [[String]] = .init(repeating: .init(repeating: "", count: c), count: r)
let dy = [-1, 0, 1, 0]; let dx = [0, 1, 0, -1]
var firePos: [(Int, Int)] = []; var humanPos: (Int, Int) = (0, 0)
var ret = 0

for row in 0..<r {
    adj[row] = readLine()!.enumerated().map { col, char in
        if char == "F" {
            firePos.append((row, col))
        } else if char == "J" {
            humanPos = (row, col)
        }
        return String(char)
    }
}

var q = Queue<(Int, Int)>()
for fire in firePos {
    q.enqueue(fire)
    visited[fire.0][fire.1] = 1
}

while(!q.isEmpty) {
    guard let there = q.front else { break }
    _ = q.dequeue()

    for i in 0..<4 {
        let ny = dy[i] + there.0
        let nx = dx[i] + there.1

        if ny < 0 || nx < 0 || ny >= r || nx >= c || visited[ny][nx] != Int.max || adj[ny][nx] == "#" {
            continue
        }
        visited[ny][nx] = visited[there.0][there.1] + 1
        q.enqueue((ny, nx))
    }
}

q.enqueue(humanPos)
humanVisited[humanPos.0][humanPos.1] = 1

while(!q.isEmpty) {
    guard let there = q.front else { break }
    _ = q.dequeue()

    if there.0 == r-1 || there.0 == 0 || there.1 == c-1 || there.1 == 0 {
        ret = humanVisited[there.0][there.1]
        break
    }

    for i in 0..<4 {
        let ny = dy[i] + there.0
        let nx = dx[i] + there.1

        if ny < 0 || nx < 0 || ny >= r || nx >= c || humanVisited[ny][nx] != 0 || adj[ny][nx] == "#" {
            continue
        }

        if visited[ny][nx] <= humanVisited[there.0][there.1] + 1 {
            continue
        }

        humanVisited[ny][nx] = humanVisited[there.0][there.1] + 1
        q.enqueue((ny, nx))
    }
}

print(ret == 0 ? "IMPOSSIBLE" : ret)