[Swift] 백준 골드4) 녹색 옷 입은 애가 젤다지?

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

1. 문제이해

• “젤다의 전설” 게임에서 화폐 단위는 루피
• 간혹 “도둑루피”라 불리는 루피도 존재하는데, 이걸 획득하면 소지한 루피가 감소하게 된다
• 주인공은 N x N 동굴에서 제일 왼쪽 위(map[0][0])에서 시작해서 제일 오른쪽 아래 칸인 map[N-1][N-1]까지 이동해야 하며, 한 번에 상하좌우 한칸씩 이동할 수 있다.
• 모든 칸에 도둑루피가 존재하며 시작점부터 도착점까지 잃는 금액을 최소로 하여 이동하려고 할 때 링크가 잃을 수 밖에 없는 최소 금액을 구하라
• 케이스마다 N과 N x N만큼의 동굴에 있는 도둑루피가 주어짐

2. 설계

• 동굴 크기와 같은 최단경로 테이블 result를 최댓값으로 초기화
• 시작점 result[0][0]을 동굴의 시작점으로 초기화 → result[0][0] = map[0][0]
• 시작점으로 초기화된 queue로 BFS
  • 현재 위치에서 이동할 수 있는 상하좌우 좌표 탐색
  • 최단경로테이블[현재.x][현재.y] + 동굴[이동.x][이동.y] < 최단경로테이블[이동.x][이동.y] 일 때 큐에 이동할 수 있는 좌표를 넣고 최단경로 테이블에 최소값 업데이트

3. 코드

func solution(){
    var t = 0
    while true{
        let N = Int(readLine()!)!
        if N == 0 { break }
        t += 1
        var map = [[Int]]()
        for _ in 0..<N{
            map.append(readLine()!.split(separator: " ").map{Int(String($0))!})
        }
        // 촤단경로 테이블 생성
        var result = Array(repeating: Array(repeating: 1000000, count: N), count: N)
        // 최단경로 테이블 시작점에 동굴 시작점의 도둑루피로 초기화
        result[0][0] = map[0][0]
        
        // 시작점으로 큐 초기화
        var queue = [(0,0)]
        
        while !queue.isEmpty{
            let dx = [0, 0, 1, -1] 
            let dy = [1, -1, 0, 0]
            var newQueue = [(Int, Int)]()

            for q in queue{ // == queue.removeLast()
                for i in 0..<dx.count{
                    let nx = q.0 + dx[i] 
                    let ny = q.1 + dy[i] 
                    if nx >= 0, nx < N, ny >= 0, ny < N{ // 이동 가능 범위
		                    // 최단[현재.x][현재.y] + 동굴[이동.x][이동.y] < 최단[이동.x][이동.y]
                        if result[q.0][q.1] + map[nx][ny] < result[nx][ny]{
                            newQueue.append((nx,ny))
                            result[nx][ny] = min(result[q.0][q.1] + map[nx][ny], result[nx][ny])
                        }
                    }
                }
            }
            queue = newQueue
        }
        print("Problem \(t): \(result[N-1][N-1])")
    }
}
solution()