[구름톤 챌린지 #19] 대체 경로

문제19. 대체 경로

구름LEVEL

---

---

문제 해결 방법

가중치가 없는 그래프의 최단 경로 탐색 방법에 대한 문제이다. 가중치가 있는 그래프에 대해서는 다익스트라 알고리즘, 벨만-포드 알고리즘, 플루이드 워샬 알고리즘 등을 고려해야 했겠지만, 가중치가 없는 그래프에 대해서는 BFS만을 이용해서 해결할 수 있다.

 

BFS 알고리즘의 특성상, 먼저 큐에 들어간 노드부터 큐에서 꺼내어 쓰기 때문에, 출발지로부터 같은 거리만큼 떨어진 노드는 같은 타이밍에 큐에서 꺼내지게 된다. 당연한 말이지만, 더 멀리 떨어진 노드를 탐색하려면, 가까웠던 노드를 통해서 가야하기 때문에 더 멀리 떨어진 노드보다 가까이에 있는 노드가 더 먼저 탐색된다. 따라서 큐에 값을 삽입할 때 거리를 업데이트하고, 이미 업데이트된 노드들은 업데이트하지 않도록 한다면, 업데이트된 모든 노드가 최단 경로를 갖게 된다.

 

한편, 오늘 알고리즘에는 특별한 조건이 붙어있다. 갈 수 없는 노드가 있는 것이다. 갈 수 없는 노드를 처리하는 방법은 사실 간단하다. 갈 수 없는 곳은 미리 방문 처리를 하면 된다. 방문 처리된 노드는 업데이트 되지도 않고, 큐에 들어가서 다른 노드의 거리를 업데이트 하지도 않기 때문에 아무 상관 없는 노드가 된다.

 

위 내용을 코드로 구현하면 아래와 같다.

import sys
from collections import deque

n, m, s, e = map(int, sys.stdin.readline().split())

graph = [[] for i in range(n + 1)]

for i in range(m):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

dq = deque()

#n일 동안 반복
for i in range(1, n + 1):
    # 시작점/끝점이 공사 중일 경우
    if i == s or i == e:
        print(-1)
        continue


    # s->node까지 가는데 최소거리를 나타내는 mapping 정보
    # -1로 초기화해서 도달하지 못하는 곳은 -1로 남게됨.
    distance_from_s = {}
    for node in range(1, n + 1):
        distance_from_s[node] = -1
    # 출발지점도 거쳐간 도시 하나임
    distance_from_s[s] = 1

    visited = {s}
    dq.append(s)
    #i를 그냥 방문처리 해버려서 길이 업데이트 되지 않도록 하면 가지 못하는 곳이 된다.
    visited.add(i)

    while dq:
        from_node = dq.popleft()
        for to_node in graph[from_node]:

            #너비 우선 탐색이므로 visited에 이미 들어가있는 값은 이미 최솟값(or 도달하지 못하는 곳)
            #가중치가 없으므로, 적은 깊이의 노드들을 먼저 큐에서 꺼내 체크하게 된다.
            if to_node not in visited:
                visited.add(to_node)
                # print(from_node, "->", to_node, ", 현재 from_node 값은 ", distance_from_s[from_node])
                # 직전 도시로부터 한칸 더 이동했음
                distance_from_s[to_node] = distance_from_s[from_node] + 1
                dq.append(to_node)

    print(distance_from_s[e])

---

최적화의 여지

위의 코드로도 제출했을 때 문제없이 모든 테스트 케이스를 통과하여 정답처리 되기는 하지만, 한가지 아쉬운 점이 있다. 바로 모든 노드에 대한 최단 경로를 구한다는 점이다. 예를 들어 출발지와 도착지가 한 칸 떨어져 있는 곳이라면, 사실 다른 노드를 고려할 것 없이, 두 노드만 고려하면 된다. 그런데 위 코드는 모든 노드에 대해 탐색하기 때문에, 경우에 따라서 비효율적으로 동작할 수 있다. 그렇다면 위 코드를 최적화 하려면 어떻게 해야할까? 도착지에 도달했다면 업데이트를 멈추고 바로 결과를 반환할 수 있게 하면 된다. 위 코드 기준으로는 큐에 더 이상 데이터가 없으면 업데이트가 종료되기 때문에, 큐를 비우고 반복문에서 빠져나오면 된다.

 

위 내용을 코드로 구현하면 아래와 같다.

import sys
from collections import deque

n, m, s, e = map(int, sys.stdin.readline().split())

graph = [[] for i in range(n + 1)]

for i in range(m):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

dq = deque()

#n일 동안 반복
for i in range(1, n + 1):
    # 시작점/끝점이 공사 중일 경우
    if i == s or i == e:
        print(-1)
        continue


    # s->node까지 가는데 최소거리를 나타내는 mapping 정보
    # -1로 초기화해서 도달하지 못하는 곳은 -1로 남게됨.
    distance_from_s = {}
    for node in range(1, n + 1):
        distance_from_s[node] = -1
    # 출발지점도 거쳐간 도시 하나임
    distance_from_s[s] = 1

    visited = {s}
    dq.append(s)
    #i를 그냥 방문처리 해버려서 길이 업데이트 되지 않도록 하면 가지 못하는 곳이 된다.
    visited.add(i)

    while dq:
        from_node = dq.popleft()
        for to_node in graph[from_node]:

            #너비 우선 탐색이므로 visited에 이미 들어가있는 값은 이미 최솟값(or 도달하지 못하는 곳)
            #가중치가 없으므로, 적은 깊이의 노드들을 먼저 큐에서 꺼내 체크하게 된다.
            if to_node not in visited:
                visited.add(to_node)
                # print(from_node, "->", to_node, ", 현재 from_node 값은 ", distance_from_s[from_node])
                # 직전 도시로부터 한칸 더 이동했음
                distance_from_s[to_node] = distance_from_s[from_node] + 1
                dq.append(to_node)
								
                ##############추가된 코드##################
                if to_node == e:
                    dq.clear()
                    break
                ##############추가된 코드 끝################

    print(distance_from_s[e])