알고리즘/알고리즘 문제풀이
Dijkstra(최단거리)_programmers_SW2018 배달 [swift]
Downey
2022. 5. 17. 22:23
https://programmers.co.kr/learn/courses/30/lessons/12978
접근 방법
- 1번 마을에서 2...N번 마을까지, 갈 수 있는지 여부를 재귀를 사용하여 확인한다. -> 1차 코드
- 반복적으로 탐색하는 경로가 생기므로 효율이 떨어짐을 인식.
- 1번 마을에서 k 이하까지, 탐색 가능한 모든 경로를 탐색하여, 방문한 마을을 기록한다. -> 2차 코드.
- 아무리 용을써도 해결 할 수 없는 반례가 있었다....
- Dijkstra 알고리즘 사용... 아래는 코드의 실행순서에 따른 설명이다.
- 매개변수 road를 사용하여 2차원 배열 map을 그린다. 이 떄, i행, j열의 원소 : i번 마을에서 j번 마을로 이동시간. 간선이 없는 경우는 -1로 둔다.
- 1번 마을에서 출발한다. var distance는 1번마을에서 각 마을로 이동하는데 걸리는 최단 시간이다.
- 각 마을로의 접근 시간은 아직 알 수 없으므로, -1로 초기화 한 뒤, distance[0]은 1번 마을에서 1번 마을로 이동이므로, 0이다.
- var queue는 우선순위 queue이다. queue의 원소는 (n번 마을, 걸리는 시간) 1번 마을로부터 시작하므로, queue.append( (0,0 ) )
- 반복문은 queue의 원소가 존재하는 동안, queue는 우선순위 queue이므로, 걸리는 시간 기준으로 sort한다.
- queue의 첫번째 원소를 꺼내어, 해당 원소에 도달하는데, 필요한 시간( input.1 )과 기록된 최단 시간( dintance[input.0] )을 비교하여, 최단 시간이 더 빠르다면, 다음 원소를 꺼내고, 최단 시간이 같거나 느릴 경우, dajikstra(:)를 실행한다.
- map[start]는 start마을에서 각 마을까지의 이동 시간이다. 이 때, index == start는 n마을에서 n마을로 즉, 같은 마을로 이동하는 경우이므로 continue, length <0인 경우는, 마을간의 이동경로가 없는 경우이다.
- distance[index] < 0 인 경우는, 1번 마을에서 index마을까지의 최단 시간이 기재되지 않은 경우이다. 그러므로, 1번 마을에서 start마을 까지의 거리 + start마을에서 index 마을까지의 거리로 할당한다. > distance[index] = distance[start] + length
- distance[index] > distance[start] + length 일 경우, index마을까지의 최단거리 보다, distance[start] + length가 작거나 같으므로, 최단 거리 distance를 갱신하고, index 마을과 연결된 마을의 최단 거리를 확인 하기 위해, queue에 갱신된 정보를 추가한다.
정답 코드
더보기
class programmers_2018SWCoding_배달 {
var map = [[Int]]()
var distance = [Int]()
var queue = [(Int, Int)]()
func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
makeMap(size: N, road: road)
distance = .init(repeating: -1, count: N)
distance[0] = 0
queue.append((0, 0))
while !queue.isEmpty {
queue.sort(by: {
$0.1 < $1.1
})
let input = queue.removeFirst()
if distance[input.0] < input.1 {
continue
}
dijkstra(start: input.0)
}
return distance.filter({
$0 <= k
}).count
}
func makeMap(size: Int, road: [[Int]]) {
var tempMap = [[Int]].init(repeating: [Int].init(repeating: -1,
count: size),
count: size)
for info in road {
let targetValue = tempMap[info[0]-1][info[1]-1]
if targetValue > info[2] || targetValue < 0 {
tempMap[info[0]-1][info[1]-1] = info[2]
tempMap[info[1]-1][info[0]-1] = info[2]
}
}
map = tempMap
for i in 0..<size {
map[i][i] = 0
}
}
func dijkstra(start: Int) {
for (index,length) in map[start].enumerated() {
if index == start {
continue
}
if length < 0 {
continue
}
if distance[index] < 0 || distance[index] > distance[start] + length {
distance[index] = distance[start] + length
queue.append((index, length + distance[start]))
}
}
}
}
1차 코드
시간 초과
각 목적지에 대해 k시간 이하로 접근 가능한지 확인을 재귀를 사용하여 확인한다.
더보기
정확성 테스트
| 테스트 1 〉 | 통과 (0.37ms, 16.2MB) |
| 테스트 2 〉 | 통과 (0.12ms, 16.6MB) |
| 테스트 3 〉 | 통과 (0.20ms, 16.6MB) |
| 테스트 4 〉 | 통과 (0.17ms, 16.5MB) |
| 테스트 5 〉 | 통과 (0.34ms, 16.6MB) |
| 테스트 6 〉 | 통과 (0.17ms, 16.3MB) |
| 테스트 7 〉 | 통과 (0.24ms, 16.3MB) |
| 테스트 8 〉 | 통과 (0.18ms, 16.3MB) |
| 테스트 9 〉 | 통과 (0.09ms, 16.4MB) |
| 테스트 10 〉 | 통과 (0.37ms, 16.6MB) |
| 테스트 11 〉 | 통과 (0.39ms, 16.5MB) |
| 테스트 12 〉 | 통과 (9892.42ms, 16.6MB) |
| 테스트 13 〉 | 통과 (838.71ms, 16.6MB) |
| 테스트 14 〉 | 통과 (111.23ms, 16.8MB) |
| 테스트 15 〉 | 통과 (1698.04ms, 17MB) |
| 테스트 16 〉 | 통과 (896.62ms, 16.6MB) |
| 테스트 17 〉 | 실패 (시간 초과) |
| 테스트 18 〉 | 통과 (313.59ms, 16.4MB) |
| 테스트 19 〉 | 통과 (225.69ms, 16.9MB) |
| 테스트 20 〉 | 실패 (시간 초과) |
| 테스트 21 〉 | 통과 (812.57ms, 17.1MB) |
| 테스트 22 〉 | 통과 (3862.06ms, 16.7MB) |
| 테스트 23 〉 | 실패 (시간 초과) |
| 테스트 24 〉 | 실패 (시간 초과) |
| 테스트 25 〉 | 실패 (시간 초과) |
| 테스트 26 〉 | 통과 (1031.06ms, 17.2MB) |
| 테스트 27 〉 | 실패 (시간 초과) |
| 테스트 28 〉 | 실패 (시간 초과) |
| 테스트 29 〉 | 실패 (시간 초과) |
| 테스트 30 〉 | 통과 (418.19ms, 17.2MB) |
| 테스트 31 〉 | 실패 (시간 초과) |
| 테스트 32 〉 | 실패 (시간 초과) |
채점 결과
정확성: 68.8
합계: 68.8 / 100.0
더보기
class programmers_2018SWCoding_배달 {
struct RoadInfo {
let lhs : Int
let rhs : Int
let length : Int
func other(_ with: Int) -> Int {
if with == lhs {
return rhs
}
return lhs
}
}
var infos = [RoadInfo]()
func transform2Info(_ road: [[Int]]) -> [RoadInfo] {
var sol = [RoadInfo]()
for info in road {
let tmp = RoadInfo.init(lhs: info[0], rhs: info[1], length: info[2])
sol.append(tmp)
}
return sol
}
func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
var answer = 0
infos = transform2Info(road)
for n in 1...N {
if true == recursion(destination: n, nowPosition: 1, limit: k, movedLength: 0) {
print(n)
answer += 1
}
}
return answer
}
func recursion(destination: Int, nowPosition: Int, limit: Int, movedLength: Int) -> Bool {
if movedLength > limit {
return false
}
if destination == nowPosition {
return true
}
let nextList = infos.filter({ info in
info.lhs == nowPosition || info.rhs == nowPosition
})
for next in nextList {
// print(destination, nowPosition, limit, movedLength, next.other(nowPosition), next.length)
if true == recursion(destination: destination, nowPosition: next.other(nowPosition), limit: limit, movedLength: movedLength + next.length) {
return true
}
}
return false
}
/*
N road K result
5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4
6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4
*/
}
2차 코드
처음부터 끝까지 가면서 방문한 곳을 기록한다.
recursion마다 history를 사용하여, 방문한 곳을 다시 방문하는 경우를 제외할 수 있으며, 서로 다른 경우를 탐색 할 수 있다.
하나의 테스트가 timeout.
처음부터 끝까지 탐색하는데 오랜 시간이 걸리는 경우가 반례인 것으로 추정
더보기
정확성 테스트
| 테스트 1 〉 | 통과 (0.36ms, 16.4MB) |
| 테스트 2 〉 | 통과 (0.43ms, 16.4MB) |
| 테스트 3 〉 | 통과 (0.69ms, 16.5MB) |
| 테스트 4 〉 | 통과 (0.18ms, 16.4MB) |
| 테스트 5 〉 | 통과 (0.10ms, 16.5MB) |
| 테스트 6 〉 | 통과 (0.15ms, 16.6MB) |
| 테스트 7 〉 | 통과 (0.16ms, 16.2MB) |
| 테스트 8 〉 | 통과 (0.10ms, 16.5MB) |
| 테스트 9 〉 | 통과 (0.11ms, 16.5MB) |
| 테스트 10 〉 | 통과 (0.17ms, 16.1MB) |
| 테스트 11 〉 | 통과 (0.20ms, 16.5MB) |
| 테스트 12 〉 | 통과 (0.39ms, 16.4MB) |
| 테스트 13 〉 | 통과 (0.41ms, 16.3MB) |
| 테스트 14 〉 | 통과 (4.98ms, 16.6MB) |
| 테스트 15 〉 | 통과 (37.42ms, 16.7MB) |
| 테스트 16 〉 | 통과 (0.25ms, 16.4MB) |
| 테스트 17 〉 | 통과 (0.21ms, 16.6MB) |
| 테스트 18 〉 | 통과 (0.80ms, 16.6MB) |
| 테스트 19 〉 | 통과 (1.97ms, 17MB) |
| 테스트 20 〉 | 통과 (2.05ms, 16.6MB) |
| 테스트 21 〉 | 통과 (6.97ms, 16.8MB) |
| 테스트 22 〉 | 통과 (3.66ms, 16.5MB) |
| 테스트 23 〉 | 통과 (26.35ms, 16.8MB) |
| 테스트 24 〉 | 통과 (118.54ms, 16.6MB) |
| 테스트 25 〉 | 통과 (7.93ms, 16.9MB) |
| 테스트 26 〉 | 통과 (14.57ms, 17.1MB) |
| 테스트 27 〉 | 통과 (36.18ms, 17.2MB) |
| 테스트 28 〉 | 통과 (23.01ms, 16.8MB) |
| 테스트 29 〉 | 통과 (109.60ms, 17.1MB) |
| 테스트 30 〉 | 통과 (21.67ms, 17.2MB) |
| 테스트 31 〉 | 통과 (0.55ms, 16.6MB) |
| 테스트 32 〉 | 실패 (시간 초과) |
채점 결과
정확성: 96.9
합계: 96.9 / 100.0
더보기
struct RoadInfo {
let lhs : Int
let rhs : Int
let length : Int
func other(_ with: Int) -> Int {
if with == lhs {
return rhs
}
return lhs
}
}
var infos = [RoadInfo]()
func transform2Info(_ road: [[Int]]) -> [RoadInfo] {
var sol = [RoadInfo]()
for info in road {
let tmp = RoadInfo.init(lhs: info[0], rhs: info[1], length: info[2])
sol.append(tmp)
}
return sol
}
func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
var answer = 0
infos = transform2Info(road)
recursion(nowPosition: 1, limit: k, movedLength: 0, boundary: N)
return visited.count
}
var visited = Set<Int>()
func recursion(nowPosition: Int, limit: Int, movedLength: Int, boundary: Int, history: Set<Int> = []) {
if movedLength > limit {
visited = visited.union(history)
return
}
var newHistory = history
if !newHistory.insert(nowPosition).inserted {
visited = visited.union(history)
return
}
// let newBoundary = Set<Int>.init(1...boundary).subtracting(newHistory)
let nextList = infos.filter({ info in
info.lhs == nowPosition || info.rhs == nowPosition
})
// .filter({ info in
// !(newHistory.contains(info.lhs) && newHistory.contains(info.rhs))
// })
// .filter({ info in
// newBoundary.contains(info.rhs) || newBoundary.contains(info.lhs)
// })
for next in nextList {
recursion(nowPosition: next.other(nowPosition),
limit: limit,
movedLength: movedLength + next.length,
boundary: boundary,
history: newHistory)
}
}