문제 링크

문제 풀이 아이디어

이번 문제는 흔한 최단 거리 문제처럼 보입니다. 어떤 최단 거리 알고리즘을 사용해서 풀어볼까요?

플로이드 와샬?

어딘가를 들러서 다른 곳을 갈 때 최단거리를 구하는 대표적인 알고리즘으로 플로이드 와샬 알고리즘이 있습니다. 플로이드 와샬 알고리즘을 사용하면 모든 쌍의 최단 거리를 구할 수 있기 때문에 이 문제에도 적용해서 풀이가 가능한데요. 하지만 문제를 플로이드 와샬 알고리즘의 시간복잡도는 O(N^3) (N은 노드의 갯수)라는 것입니다. 문제의 조건에 보면 노드, 즉 지역의 갯수가 최대 100,000입니다. O(N^3)는 무리입니다.

다익스트라?

또 다른 최단거리를 구하는 대표적인 알고리즘으로는 다익스트라 알고리즘이 있습니다. 다익스트라 알고리즘은 간선의 가중치가 서로 다를 때, 그리고 음수 간선이 없을 때 사용할 수 있는데요.

주어진 문제를 보면 간선의 가중치가 다르지 않습니다. 굳이 구현이 복잡한 다익스트라 알고리즘을 쓸 필요가 없습니다. 참고로 시간복잡도는 O(ElogE) (E의 간선의 갯수)입니다. 이 문제 기준으로 E는 roads의 길이, 최대 500,000으로 시간복잡도 문제는 없을 것 같네요.

bfs!

간선의 가중치가 없는 최단거리 문제는 역시 bfs입니다. 구현도 쉽고요. 인접 행렬을 사용하면 O(N^2), 인접리스트의 방식을 활용하면 O(V+E)에 구현할 수 있습니다. 이 문제의 경우, N이 최대 100,000이고 E가 최대 500,000이므로 인접리스트 방식을 활용하는 것이 더 좋겠죠?

다만 문제는 모든 source에 대해서 bfs를 실시할 경우 시간복잡도는 O((V + E) * S) (S는 source의 길이)입니다. 하지만 bfs의 경우 완전탐색이기 때문에 원점에서 모든 다른 노드까지의 거리를 구할 수 있습니다.

⭐️ 따라서 목적지는 어차피 한 곳이므로 목적지를 원점으로 해서 완전탐색을 실시하도록 합시다!

최단 거리 알고리즘 정리

이번 포스팅에서 3가지 최단거리 알고리즘을 언제 사용해야 하는가 딱 정해놓고 가겠습니다.

bfs

간선의 가중치가 없을 때

다익스트라

간선의 가중치가 서로 다르지만 음수 간선은 없을 때

플로이드 와샬

간선의 가중치가 있고 모든 node의 쌍에 대한 거리를 구해야 할 때

코드

// 큐 구현
struct Queue {
    var index = 0
    var data = [(Int, Int)]()

    var isEmpty: Bool {
        index == data.count
    }

    mutating func push(_ int: (Int, Int)) {
        data.append(int)
    }

    mutating func pop() -> (Int, Int) {
        defer {
            index += 1
        }
        return data[index]
    }
}

func solution(_ n:Int, _ roads:[[Int]], _ sources:[Int], _ destination:Int) -> [Int] {
    
    // 인접 리스트 (인접한 배열 저장)
    var map = Array(repeating: [Int](), count: n + 1)
    
    for road in roads {
        map[road[0]].append(road[1])
        map[road[1]].append(road[0])
    }
    
    // 목적지까지의 거리 저장하는 배열
    var distance = Array(repeating: -1, count: n + 1)
    
    // 목적지를 출발점으로 해서 각 지점까지의 거리 bfs로 측정
    func bfs() {
        var q = Queue()
        q.push((destination, 0))
        distance[destination] = 0
        
        while !q.isEmpty {
            let (now, cost) = q.pop()
            for next in map[now] {
                if distance[next] == -1 {
                    q.push((next, cost + 1))
                    distance[next] = cost + 1
                }
            }
        }
    }
    
    bfs()

    return sources.map { distance[$0] }
}