[Swift] 18352. 특정 거리의 도시 찾기

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

18352번: 특정 거리의 도시 찾기

 

---

 

 

그래프, 다익스트라 연습을 하려고 시도했던 문제이다.

기존에 그래프를 순회할 때 아래처럼 많이 사용했었는데, 시간초과가 나서 idx로 큐에 접근하는 방법으로 수정했다.

while let q = queue.isEmpty() ? nil : queue.removeFirst()

 

X부터 큐(일반 배열)에 넣음 (거리배열dist는 max값으로 초기화, 시작점은 0 넣어주기)
"현재 idx 거리 +1 < 다음 idx 거리" 이면 거리 업데이트, 큐에 추가
idx가 queue배열크기보다 커지면 반복 종료(더이상 방문할 정점이 없음을 뜻함)

let NMKX = readLine()!.split(separator: " ").map { Int($0)! }
let (N, M, K, X) = (NMKX[0],NMKX[1],NMKX[2],NMKX[3])
var list: [[Int]] = Array(repeating: [], count: N+1)

for _ in 0..<M {
    let tmp = readLine()!.split(separator: " ").map { Int($0)! }
    let (st, ed) = (tmp[0], tmp[1])
    list[st].append(ed)
}
var dist = Array(repeating: Int.max, count: N+1)
dist[X] = 0

var queue: [Int] = [X]
var ansList:[Int] = []
var idx = 0

while idx < queue.count {
    let now = queue[idx]
    idx += 1
    
    for n in list[now] {
        if dist[n] > dist[now]+1 {
            dist[n] = dist[now]+1
            queue.append(n)
            if dist[n] == K {
                ansList.append(n)
            }
        }
    }
}

if ansList.isEmpty {
    print("-1")
} else {
    ansList.sorted().forEach { print($0) }
}