https://www.acmicpc.net/problem/4485
다익스트라 알고리즘으로 접근한 문제다.
풀이
너비우선탐색을 수행한다. 다익스트라 알고리즘의 특성상 우선순위 큐를 사용해서 풀어야 하지만, 문제의 N값이 크지 않기에 배열을 정렬하여 풀어도 시간초과는 피할 수 있다. 스위프트의 경우 우선순위큐를 직접 구현해야하기에 귀찮다.
방문여부를 저장할 2차원 visited 배열, 각 좌표에 도둑루피의 값을 담을 2차원 map 배열과 해당좌표까지의 최저 cost를 담을 2차원 cost배열을 생성한다. cost 배열은 INF로 초기화한 뒤 탐색을 수행한다.
x, y, cost 정보를 담아낼 배열을 생성한다. 배열에서 cost가 가장 작은 좌표를 먼저 방문하여 (현재 좌표의 cost + 인접배열의 cost값)을 계산하여 인접배열의 cost를 더 작은 값으로 갱신한다. 다음 탐색에 cost가 가장 작은 값을 방문해야 하니 매 반복문의 마지막에는 큐를 정렬해 준다.
탐색이 끝나면 목적지인 cost배열의 가장 마지막 값을 출력하면 된다.
정답 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Foundation | |
var ans = [String]() | |
let INF = Int.max | |
var T = 1 | |
while let line = readLine(){ | |
if line == "0"{ | |
break | |
} | |
let N = Int(line)! | |
var map = Array(repeating: Array(repeating: 0, count: N), count: N) | |
var cost = Array(repeating: Array(repeating: INF, count: N), count: N) | |
var visited = Array(repeating: Array(repeating: false, count: N), count: N) | |
let dx = [-1,1,0,0] | |
let dy = [0,0,-1,1] | |
var q = [(x:Int,y:Int,cost:Int)]() | |
for i in 0..<N{ | |
let line = readLine()!.split(separator: " ").map{Int($0)!} | |
for k in 0..<N{ | |
map[i][k] = line[k] | |
} | |
} | |
q.append((0,0,map[0][0])) | |
while !q.isEmpty{ | |
let curr = q.removeLast() | |
let x = curr.x | |
let y = curr.y | |
visited[x][y] = true | |
cost[x][y] = min(cost[x][y], curr.cost) | |
for i in 0..<4{ | |
let nx = x+dx[i] | |
let ny = y+dy[i] | |
if nx<0 || nx>=N || ny<0 || ny>=N || visited[nx][ny]{ continue } | |
q.append((nx,ny,cost[x][y]+map[nx][ny])) | |
} | |
q.sort(by: {$0.cost>$1.cost}) | |
} | |
ans.append("Problem \(T): \(cost[N-1][N-1])") | |
T += 1 | |
} | |
print(ans.joined(separator: "\n")) |
'Problem Solving > BOJ' 카테고리의 다른 글
[17144] 미세먼지 안녕! (0) | 2023.02.07 |
---|---|
[4836] 춤 (0) | 2023.02.06 |
[3048] 개미 (0) | 2023.02.04 |
[14466] 소가 길을 건너간 이유 6 (0) | 2023.02.03 |
[14464] 소가 길을 건너간 이유 4 (0) | 2023.02.01 |