프로그래머스 (최단거리), 다익스트라 이해하기

문제 링크

문제 요약

주어진 모든 edge 들 의 최단거리를 구하고 1 에서부터 K 범위 만큼 떨어져있는 node 의 갯수를 구하는 문제

Given:

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

첫번째 Test

두번째 Test

시도 1

• 접근 방법
  • 주어진 그래프에서 각 edge 들의 최단 거리를 구하기 위해서 initial 노드 부터 N 번째 노드까지의 최단 edge 의 값을 차례대로 계산했다. (주어진 첫번째 Test 에 맞춰서 문제를 풀기 시작했다)
  • 각 Connected Edges 들은 [Source 노드, 목적지 노드, Source 노드 에서 목적지 노드까지의 거리] 라고 이해 했다.

1.0 주어진 Road 의 정보에 따라 Graph 를 아래와 같이 작성했다.

2.0 Queue 에 차례대로 첫번째 노드부터 5번째 노드까지 넣어주었다.

3.0 각 Edge 의 최적 값을 기록할 Distance 배열을 아래와 같이 초기화 시켜주었다. (0 인덱스->첫번째 노드, distance 값->0)

Distance 배열 초기화

4.0 첫번째 노드에서 부터 연결 되어 있는 Edge 들의 정보를 아래와 같은 순서대로 비교하고 Distance 배열을 업데이트 시켜주었다.

- Queue 에서 첫번째 노드인 1 에 연결되어 있는 Edge 들을 아래와 같이 Connected Edges 을 Graph 에서 빼내 온다.

1번째 노드 에서 2 번째 노드 까지의 거리 : 1

1번째 노드 에서 4 번째 노드 까지의 거리 : 2

현재 Distance 의 2,4 노드의 거리값 : ∞

이때 Distance 에 저장 되어 있던 각 노드의 거리 값을 `SavedDistance` 라고 부르고

새롭게 계산 되어지는 거리값을 `NewDistance` 라고 불렀다.

`NewDistance` = Source노드의 `SavedDistance` + Edge 에 있는 목적지 까지의 거리의 값

Ex) `NewDistance` 는 Edge 가 [1 2 1] 일때

Distance 배열의 1번째 노드의 값(`SavedDistance`) = 0

주어진 Edge 의 목적지 까지의 거리 = 1

`NewDistance` = 0 + 1 = 1

만약 현재 목적지 의 `SavedDistance` 값이 위에서 계산된 `NewDistance` 값보다 클시, `Distance` 배열을 업데이트 시켜준다.

즉 주어진 Edge 의 정보를 바탕으로 Source 노드 까지 온거리 + Source -> 목적지 까지 의 거리 값이 현재 저장되어 있던 거리값보다 작을시 저장된 거리값을 업데이트 시켜주는 방식이다.

- 1번째 노드 부터 5번째 노드까지의 거리 계산.

최종 Distance

이 계산 방법을 거치면 첫번째 Test case 의 결과 값은 주어진 K = 3,

1 에서 배달 가능한 노드의 개수 = 3 로 테스트 를 통과 하지 못한다.

문제 분석

1.0 Queue 에 넣은 노드의 순서가 문제일까?

• 현재로써는 Queue 에 모든 노드를 넣고 하나씩 돌면서 최단 Edge Cost 를 구하는게 문제가 있을것 같지 않다고 판단한다.
• 따라서 Queue 첫번째 노드부터 마지막 노드를 할당하고 하나씩 빼오는데, 아무것도 없을때까지 위 계산을 반복하는건 그대로 유지 시킨다.

2.0 단방향 으로 할당 되어 있는 Edge 정보들

• 현재 Graph 에 저장되어 있는 Edge 들의 정보는 단방향으로 설정되어 있다. 주어진 문제는 양방향 Edge cost 가 측정 되어 있기 때문에 각 Source, 목적지 노드 에 Edge Cost 를 할당시켜줘야한다.
• 양방향, 단방향 이 실질적인 계산에 어떻게 영향을 아래 다음 시도에서 알아봤다.

시도 2

• 접근 방법
  • 주어진 그래프에서 각 edge 들의 최단 거리를 구하기 위해서 initial 노드 부터 N 번째 노드까지의 최단 edge 의 값을 차례대로 계산했다. (주어진 첫번째 Test 에 맞춰서 문제를 풀었다)
  • 주어진 Edge 를 양방향 으로 인식하고 Graph 를 만들었다.

양방향인 Edge 를 고려한 Graph

• 시도 1에서 반영한 최단 거리 공식을 똑같이 적용해서 표로 나타내면 아래와 같이 표현 할수있다.

Table 1.0 : Edge 를 양방향 으로 적용 했을때 결과표

Edge 를 양방향 으로 적용

Edge 양방향으로 적용하고 계산한 결과는 K = 3 일때 1,2,4,5 노드와 연결이 가능해졌다.

이렇게 첫번째 케이스는 통과가 됐는데 어떤 영향이 있었던걸까?

Table 2.0 : Edge 의 단방향 vs 양방향 결과 비교

양방향 을 고려 하지 않을시 나타나는 문제점은 이 예제에서 2번째, 4번째 노드에서 5번째 노드로 접근할때 발생한다.

양방향일 경우 2번째 노드에서 5,3번째 노드로 접근하는 거리를 계산할수 있었지만,

단방향일때 5번째 노드는 4번째 노드차례가 올때까지 업데이트 될수 없는 상황에 처하게 된다.

이번 시도는 테스트 케이스는 통과 하지만, 정확성 검사에서 실패하고 만다.

문제 분석

1.0 Queue 에 넣은 노드의 순서가 문제일까?

• 앞서 나타난 단방향, 양방향일때의 문제점에서 `노드의 차례` 따라서 Edge 의 최적 거리 값이 변화되는것을 알수 있었다.
• 만약에 오직 특정노드 를 지나서 도달할수 있는 노드가 있다면 어떻게 될까?*
  • 현재 Queue 에서는 1 부터 5 까지 차례대로 연결된 Edge 들을 계산한다. 하지만 아래와 같은 그래프가 주어진다면 결과는 어떻게 될까?

Given :

N = 5

Road = [[1, 2, 4], [1, 3, 1], [3, 4, 1], [4, 2, 1], [2, 5, 1]]

K = 4

Solution:

5

Table 3.0 : 특정 노드를 지나서 도달할수 있는 노드 example

양방향 Edge 를 적용한다고 해도 Queue 의 순서가 1 부터 5까지 순서대로 라면,

5번째 노드는 아래 그림처럼 1 -> 3 -> 4 -> 2 -> 5

를 지나가야 최적의 edge 를 계산할수 있다.

하지만 1부터 순차적으로 할당되어 있는 Queue 에선 노드 2 에서 5 로 갈수 있는 방법이 존재 하지 않는다.

따라서 Queue 를 특정한 기준을통해 동적 으로 append 해주는 과정이 필요하다.

시도 3 - 다익스트라

• 접근 방법
  • 주어진 Edge 를 양방향 으로 인식하고 Graph 를 만든다.
  • InitialNode 를 Queue 에 할당한다. (Queue 에 첫번째 노드 정보인 (1,1,0) 만 할당)
  • 각 Edge 의 정보가 업데이트 될때마다 해당 Edge 를 업데이트된 Cost 와 같이 Queue 에 집어 넣는다. 이렇게 되면 Queue 에는 중복된 목적지 노드 가 생기는데 아래와 같이 처리해준다.
  • 큐에서 꺼내온 목적지 까지의 도착비용을 가진 Edge 가 저장되어 있는 목적지 노드 까지의 비용보다 많이 든다면, 목적지 노드 로 향하는 최적의 Cost 가 아니기때문에 계산을 Skip 한다.
  • 거리 계산은 오로지 큐에서 꺼내온 Edge 의 Cost 값이 더 작거나 같을때 진행된다.
  • 즉 특정 노드에 더 적은 비용으로 도착할수 있는 경로로 계산한다.

ex) 2 노드 까지 도착할수 있는 루트는 1 -> 2 , 1 -> 3 -> 4 -> 2 로 2가지 방법이 있다. 첫번째 루트는 [1 2 4]

두번째 루트는 [1 3 1] -> [3 4 2] -> [3 4 3]

따라서 두번째 루트의 비용이 첫번째 루트의 비용보다 적기 때문에 [1 2 4] edge 가 Queue 에서 나올경우 1->2->5 , 1->2->4 까지 가는 경로 의 비용 계산은 스킵된다.

Graph 와 Queue 초기화

큐에서 첫번째 Edge 정보를 기존 Distance 값 에 대입

Queue 에서 첫번째로 빼온 Edge 값 : 1 1 0 (1 에서 1로 가는 cost = 0)

초기에 저장된 1 번 노드 의 Distance 값: 0

Distance[0] < 0 , false 따라서 1번 노드와 연결되어 있는 Edge 들의 정보를 계산할수 있다.

(큐에서 나온 Edge 의 cost 가 지금 까지 계산된 SourceNode 에서부터 목적지Node 까지의 최적의 거리 이기 때문에)

Edge1 = [1 2 4]

@Node 2, currently `savedCost` = inf

`newCost` = 0 + 4 = 4

`SavedCost` > `newCost`

∴ Update @Node 2 with `newCost` & append [1 2 `newCost`] into Queue

Edge2 = [1 3 4]

@Node 3, currently `savedCost`= inf

`newCost` = 0 + 1 = 1

∴ Update @Node 3 with `newCost` & append [1 3 `newCost`] into Queue

Queue 에서 첫번째로 빼온 Edge 값 : 1 2 4 (1 에서 2로 가는 cost = 4)

초기에 저장된 2 번 노드 의 Distance 값: 4

Distance[1] < 4 , false 따라서 2번 노드와 연결되어 있는 Edge 들의 정보를 계산할수 있다.

(큐에서 나온 Edge 의 cost 가 지금 까지 계산된 SourceNode 에서부터 목적지Node 까지의 최적의 거리 이기 때문에)

Edge1 = [2 1 4]

@Node 1, currently `savedCost` =0

`newCost` = 4 + 4 = 8

`SavedCost` < `newCost`

∴ Neither updating on Distance element nor appending into Queue

Edge2 = [2 4 1]

@Node 4, currently `savedCost`= inf

`newCost` = 4 + 1 = 5

`SavedCost` > `newCost`

∴ Update @Node 4 with `newCost` & append [2 4 5] into Queue

Edge3 = [2 5 1]

@Node 5, currently `savedCost`= inf

`newCost` = 4 + 1 = 5

∴ Update @Node 5 with `newCost` & append [2 5 5] into Queue

Queue 에서 첫번째로 빼온 Edge 값 : 1 3 1 (1 에서 3로 가는 cost = 1)

초기에 저장된 3 번 노드 의 Distance 값: 1

Distance[2] < 1 , false 따라서 3번 노드와 연결되어 있는 Edge 들의 정보를 계산할수 있다.

(큐에서 나온 Edge 의 cost 가 지금 까지 계산된 SourceNode 에서부터 목적지Node 까지의 최적의 거리 이기 때문에)

Edge1 = [3 1 1]

@Node 1, currently `savedCost` =0

`newCost` = 1 + 1 = 2

`SavedCost` < `newCost`

∴ Neither updating on Distance element nor appending into Queue

Edge2 = [3 4 1]

@Node 4, currently `savedCost`= 5

`newCost` = 1 + 1 = 2

`SavedCost` > `newCost`

∴ Update @Node 4 with `newCost` & append [3 4 2] into Queue

Queue 에서 첫번째로 빼온 Edge 값 : 2 4 5 (2 에서 4로 가는 cost = 5)

초기에 저장된 4 번 노드 의 Distance 값: 2

Distance[3] < 5 , true 기존 4로 향하는 cost 가 더 적음

따라서 4번 노드와 연결되어 있는 Edge 들의 정보를 계산x

Queue 에서 첫번째로 빼온 Edge 값 : 2 5 5 (2 에서 5로 가는 cost = 5)

초기에 저장된 5 번 노드 의 Distance 값: 5

Distance[4] < 5 , false 따라서 5번 노드와 연결되어 있는 Edge 들의 정보를 계산할수 있다.

(큐에서 나온 Edge 의 cost 가 지금 까지 계산된 SourceNode 에서부터 목적지Node 까지의 최적의 거리 이기 때문에)

Edge1 = [5 2 1]

@Node 2, currently `savedCost` = 4

`newCost` = 5 + 1 = 6

`SavedCost` < `newCost`

∴ Neither updating on Distance element nor appending into Queue

Queue 에서 첫번째로 빼온 Edge 값 : 3 4 2(3 에서 4로 가는 cost = 2)

초기에 저장된 4 번 노드 의 Distance 값: 2

Distance[3] < 2, false 따라서 3번 노드와 연결되어 있는 Edge 들의 정보를 계산할수 있다.

(큐에서 나온 Edge 의 cost 가 지금 까지 계산된 SourceNode 에서부터 목적지Node 까지의 최적의 거리 이기 때문에)

Edge1 = [4 3 1]

@Node 3, currently `savedCost` =1

`newCost` = 2 + 1 = 3

`SavedCost` < `newCost`

∴ Neither updating on Distance element nor appending into Queue

Edge2 = [4 2 1]

@Node 2, currently `savedCost`= 4

`newCost` = 2 + 1 = 3

`SavedCost` > `newCost`

∴ Update @Node 2 with `newCost` & append [4 2 3] into Queue

Queue 에서 첫번째로 빼온 Edge 값 : 4 2 3 (4 에서 2로 가는 cost = 3)

초기에 저장된 2 번 노드 의 Distance 값: 3

Distance[1] < 3, false 따라서 3번 노드와 연결되어 있는 Edge 들의 정보를 계산할수 있다.

(큐에서 나온 Edge 의 cost 가 지금 까지 계산된 SourceNode 에서부터 목적지Node 까지의 최적의 거리 이기 때문에)

Edge1 = [2 1 4]

@Node 1, currently `savedCost` = 0

`newCost` = 3 + 4 = 7

`SavedCost` < `newCost`

∴ Neither updating on Distance element nor appending into Queue

Edge2 = [2 4 1]

@Node 4, currently `savedCost`= 2

`newCost` = 3 + 1 = 4

`SavedCost` < `newCost`

∴ Neither updating on Distance element nor appending into Queue

Edge3 = [2 5 1]

@Node 5, currently `savedCost`= 5

`newCost` = 3 + 1 = 4

`SavedCost` > `newCost`

∴ Update @Node 2 with `newCost` & append [2 5 4] into Queue

Queue 에서 첫번째로 빼온 Edge 값 : 2 5 4 (2 에서 5로 가는 cost = 4)

초기에 저장된 5 번 노드 의 Distance 값: 4

Distance[4] < 4, false 따라서 3번 노드와 연결되어 있는 Edge 들의 정보를 계산할수 있다.

(큐에서 나온 Edge 의 cost 가 지금 까지 계산된 SourceNode 에서부터 목적지Node 까지의 최적의 거리 이기 때문에)

Edge1 = [5 2 1]

@Node 2, currently `savedCost` = 3

`newCost` = 4 + 1 = 5

`SavedCost` < `newCost`

∴ Neither updating on Distance element nor appending into Queue

최종 Distance Queue, 및 거쳐온 Node 순서

K = 4, 배달 가능한 Node 의 개수 = 5 개

코드로 작성한 세번째 방법

struct Node: Hashable {
  let index: Int


  func hash(into hasher: inout Hasher) {
    return index.hash(into: &hasher)
  }

  static func == (lhs: Node, rhs: Node) -> Bool {
    return lhs.index == rhs.index
  }

}


struct Edge <T> {
  let source: Node?
  let destination: Node?
  var weight: Int
}

class AdjacencyList<T> {

  var adjacencies: [Node: [Edge<T>]] = [:]

  func createNode(index:Int) -> Node {
    let node = Node(index: index)
    adjacencies[node] = []
    return node
  }

  func addEdge(source: Node, destination: Node, weight: Int){
    let edge1 = Edge<T>(source: source, destination: destination, weight: weight)
    adjacencies[source]?.append(edge1)
  }

  func edges(from source: Node) -> [Edge<T>] {
    return adjacencies[source] ?? []
  }

}


func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {

  let graph = AdjacencyList<Int>()

  //Contains information of everysingle Nodes.
  let nodeContainer = (1...N).map({graph.createNode(index: $0)})

  var queue =  [Edge<Int>(source: nodeContainer.first, destination: nodeContainer.first, weight: 0)]
  var optimalDistance: [Int] = Array(repeating: Int.max, count: N+1)
  optimalDistance[1] = 0

  road.forEach({
    graph.addEdge(source: nodeContainer[$0.first!-1], destination: nodeContainer[$0[1]-1], weight: $0.last!)
    graph.addEdge(source: nodeContainer[$0[1]-1], destination: nodeContainer[$0.first!-1], weight: $0.last!)
  })


  while !queue.isEmpty {
    let currentEdge = queue.removeFirst()
    if optimalDistance[currentEdge.destination!.index] < currentEdge.weight {continue}

    for edge in graph.edges(from: currentEdge.destination!) {
      let savedCost = optimalDistance[edge.destination!.index]
      let nextCost =  optimalDistance[edge.source!.index] + edge.weight
      if savedCost > nextCost {
        optimalDistance[edge.destination!.index] = nextCost
        queue.append(edge)
      }
    }
  }

  return optimalDistance.filter({$0 <= k}).count
}