Swift 문제풀이

[Gold III] 벽 부수고 이동하기 - 2206

문제 링크

성능 요약

메모리: 188168 KB, 시간: 364 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 7월 20일 18:49:21

문제 설명

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

시간초과 코드

func Q_2206() {
    let way = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    let nm = readLine()!.split { $0 == " " }.map { Int($0)! }
    let (n, m) = (nm[0], nm[1])
    var grid = [[Int]]()
    // x, y ,distance, destroy
    var queue = [(Int, Int, Int, Int)]()

    for _ in 0 ..< n {
        let input = readLine()!.map { Int(String($0))! }
        grid.append(input)
    }
    
    print(bfs(0, 0, 1, 0))
    
    func bfs(_ x: Int, _ y: Int, _ distance: Int, _ destroy: Int) -> Int {
        var answer = -1
        queue.append((x, y, distance, destroy))
        while !queue.isEmpty {
            let (qx, qy, qdistance, qdestroy) = queue.removeFirst()
            if (qx, qy) == (n - 1, m - 1) {
                answer = qdistance
                break
            }

            for (dx, dy) in way {
                let nx = qx + dx
                let ny = qy + dy
                if isValid(nx, ny) {
                    if grid[nx][ny] == 0 {
                        queue.append((nx, ny, qdistance + 1, qdestroy))
                    } else if grid[nx][ny] == 1 && qdestroy == 0 {
                        queue.append((nx, ny, qdistance + 1, qdestroy + 1))
                    }
                }
            }
        }
        return answer
    }

    func isValid(_ x: Int, _ y: Int) -> Bool {
        return x >= 0 && x < n && y >= 0 && y < m
    }

}

정답 코드

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

var visited = [[[Bool]]](repeating: [[Bool]](repeating: [Bool](repeating: false, count: m), count: n), count: 2)

func isValidCoord(y: Int, x: Int) -> Bool {
    return 0..<n ~= y && 0..<m ~= x
}

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

var queue = [(0, 0, 1, 0)]
var index = 0
var answer = -1

while queue.count > index {
    let y = queue[index].0
    let x = queue[index].1
    let d = queue[index].2
    let brokenCount = queue[index].3
    
    if y == n - 1 && x == m - 1 {
        answer = d
        break
    }
    
    for i in 0..<4 {
        let ny = y + dy[i]
        let nx = x + dx[i]
        
        if !isValidCoord(y: ny, x: nx) || visited[brokenCount][ny][nx] {
            continue
        }
        
        if graph[ny][nx] == "0" {
            visited[brokenCount][ny][nx] = true
            queue.append((ny, nx, d + 1, brokenCount))
        }
        
        if graph[ny][nx] == "1" && brokenCount == 0 {
            visited[brokenCount + 1][ny][nx] = true
            queue.append((ny, nx, d + 1, brokenCount + 1))
        }
        
    }
    index += 1
}

print(answer)

gpt 분석

시간 복잡도 비교
두 코드 모두 BFS를 사용하므로, 각각의 시간 복잡도는 동일하게
O(n×m)입니다. 이는 격자의 모든 칸을 최대 두 번 방문할 수 있기 때문입니다 (벽을 부순 경우와 부수지 않은 경우).

효율성 비교
큐 관리:

첫 번째 코드에서는 queue.removeFirst()를 사용하여 큐의 첫 번째 요소를 제거합니다. 이는 O(n)의 시간이 걸립니다.
두 번째 코드에서는 index를 사용하여 큐에서 요소를 꺼냅니다. 이는 O(1)의 시간 복잡도를 갖습니다.
방문 체크:

두 번째 코드에서는 3차원 배열 visited를 사용하여 방문 여부를 관리합니다. 이는 명확하고 접근이 빠릅니다.
첫 번째 코드에서는 2차원 배열의 튜플로 방문 여부를 관리합니다. 이는 가독성이 떨어질 수 있지만 동작은 유사합니다.
결론
시간 복잡도: 두 코드 모두 이론적으로 동일한 시간 복잡도를 가집니다.
효율성: 두 번째 코드가 큐 관리 측면에서 더 효율적입니다. index를 사용하여 큐를 관리하는 방식이 더 빠릅니다.
가독성: 두 번째 코드가 더 가독성이 높습니다. visited 배열을 3차원으로 관리하여 방문 여부를 명확히 구분합니다.
따라서, 두 번째 코드가 실제 실행 시간과 가독성 측면에서 더 효율적이라고 할 수 있습니다. 첫 번째 코드에서 큐 관리를 index 방식으로 변경하면 효율성이 더 좋아질 것입니다.