문제 링크 (opens new window)

풀이 (시간초과)

1. BFS + DFS

import Foundation

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

let dy = [-1, 0, 1, 0]; let dx = [0, 1, 0, -1]
var found = false; var ret = 0
var LPosition: [(Int, Int)] = []

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

    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]
        }
    }
}

struct Point: Hashable {
    var y: Int
    var x: Int
}

var iceToWaterPoints = Set<Point>()

for i in 0..<r {
    adj[i] = readLine()!.enumerated().map { index, char in
        if char == "L" {
            LPosition.append((i, index))
        }
        return String(char)
    }
}

// 1. DFS로 물 영역 순회
// 2. 얼음영역 만나면 물로 변경

func dfs(_ y: Int, _ x: Int) {
    visited[y][x] = true

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

        if ny < 0 || nx < 0 || ny >= r || nx >= c || visited[ny][nx] {
            continue
        }

        if adj[ny][nx] == "X" {
            iceToWaterPoints.insert(.init(y: ny, x: nx))
            continue
        }

        dfs(ny, nx)
    }
}

func bfs(_ start: (Int, Int)) {
    visitedBFS[start.0][start.1] = 1
    var q = Queue<(Int, Int)>()
    q.enqueue(start)

    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 || visitedBFS[ny][nx] != 0 || adj[there.0][there.1] == "X" {
                continue
            }
            q.enqueue((ny, nx))
            visitedBFS[ny][nx] = visitedBFS[there.0][there.1] + 1
        }
    }
}

while(!found) {
    for row in 0..<r {
        for col in 0..<c {
            if visited[row][col] || adj[row][col] == "X" || adj[row][col] == "L" {
                continue
            }

            dfs(row, col)
        }
    }

    bfs(LPosition.first!)

    if visitedBFS[LPosition.last!.0][LPosition.last!.1] != 0 {
        break
    }

    for iceToWater in iceToWaterPoints {
        adj[iceToWater.y][iceToWater.x] = "."
    }

    iceToWaterPoints.removeAll()
    visited = .init(repeating: .init(repeating: false, count: c), count: r)
    visitedBFS = .init(repeating: .init(repeating: 0, count: c), count: r)
    ret += 1
}

print(ret)

풀이 (정답)

1. 플러드필 - 큐 두개써서 풀이하는 방식
2. 분리된 영역 계산을 위해서 DFS가 필수적이지 않음. 오히려 재귀호출 과정에서 함수 호출에 대한 비용이 추가로 청구되므로 시간 혹은 메모리에서 초과 발생
3. 값 복사는 최대한 자제하고, swap을 사용하여 인스턴스를 지우도록 하자.

import Foundation

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

    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 adj: [[String]] = .init(repeating: .init(repeating: "", count: c), count: r)
var visitedSwan: [[Bool]] = .init(repeating: .init(repeating: false, count: c), count: r)
var visitedWater: [[Bool]] = .init(repeating: .init(repeating: false, count: c), count: r)
var swanQueue = Queue<(Int, Int)>(); var swanTempQueue = Queue<(Int, Int)>(); var waterQueue = Queue<(Int, Int)>(); var waterTempQueue = Queue<(Int, Int)>()
let dy = [-1, 0, 1, 0]; let dx = [0, 1, 0, -1]
var ret = 0
var swanPosition: [(Int, Int)] = []

for i in 0..<r {
    adj[i] = readLine()!.enumerated().map { index, char in
        if char == "L" {
            swanPosition.append((i, index))
            waterQueue.enqueue((i, index))
        } else if char == "." {
            waterQueue.enqueue((i, index))
        }
        return String(char)
    }
}

func moveSwan() -> Bool {
    while(!swanQueue.isEmpty) {
        guard let here = swanQueue.front else { break }
        _ = swanQueue.dequeue()
        visitedSwan[here.0][here.1] = true

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

            if ny < 0 || nx < 0 || ny >= r || nx >= c || visitedSwan[ny][nx] {
                continue
            }
            visitedSwan[ny][nx] = true

            if adj[ny][nx] == "X" {
                swanTempQueue.enqueue((ny, nx))
                continue
            }

            if adj[ny][nx] == "L" {
                return true
            }

            swanQueue.enqueue((ny, nx))
        }
    }

    return false
}

func meltWater() {
    while(!waterQueue.isEmpty) {
        guard let here = waterQueue.front else { break }
        _ = waterQueue.dequeue()

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

            if ny < 0 || nx < 0 || ny >= r || nx >= c || visitedWater[ny][nx] {
                continue
            }

            visitedWater[ny][nx] = true

            if adj[ny][nx] == "X" {
                waterTempQueue.enqueue((ny, nx))
                adj[ny][nx] = "."
                continue
            }

            waterQueue.enqueue((ny, nx))
        }
    }
}

swanQueue.enqueue((swanPosition.first!.0, swanPosition.first!.1))
visitedSwan[swanPosition.first!.0][swanPosition.first!.1] = true

while(true) {
    if moveSwan() { break }
    meltWater()
    swap(&swanQueue, &swanTempQueue)
    swap(&waterQueue, &waterTempQueue)

    swanTempQueue = Queue<(Int, Int)>()
    waterTempQueue = Queue<(Int, Int)>()
    ret += 1
}

print(ret)