[백준] 산책(small)

 

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

22868번: 산책 (small)

S -> E로의 최단거리를 구해 해당 경로를 위해 사용된 정점을 제외하고 E -> S로의 최단거리를 구해주면 된다. 간선의 길이가 1으로 고정이 되어있으므로 BFS를 2번 돌려서 풀이가 가능합니다. 이 문제의 포인트는 최단 경로를 위해 사용된 노드들을 기록해야하는데 이는 S -> E를 위한 BFS를 돌릴 때 현재 노드의 이전 노드를 기록해두면 됩니다. 다음 노드를 방문하려고 하는데 prev가 기록되어 있으면 이미 방문한 노드이므로 방문하지 않으면 됩니다. 각 노드에 연결된 노드들을 정렬해서 저장해 놓은 상태에서 BFS_with_prev를 돌리면 자연스럽게 사전순으로 경로가 지정되게 됩니다. 다음으로는 prev를 이용하여 S -> E 최단 경로를 위해 사용된 정점들을 방문처리를 해두고 E -> S BFS를 통해 얻은 최단 경로의 길이와 합해주면 정답이 됩니다.

 

import sys
from collections import defaultdict, deque

# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m = tuple(map(int, input().split()))

graph = defaultdict(list)

# 그래프 입력 받기
for _ in range(m):
    start, end = tuple(map(int, input().split()))
    graph[start].append(end)
    graph[end].append(start)

# s: 시작, e: 목적지
s, e = tuple(map(int, input().split()))

# 그래프와 연결되어 있는 정점들 정렬
for key in graph.keys():
    graph[key].sort()


# 현재 i번 노드를 방문하는 직전 노드를 저장해둔다.
# 각 노드와 연결되어 있는 노드들을 정렬해두었기 때문에 여러 노드들에서 방문이 가능하더라도 가장 숫자가 작은 노드를 저장하게 된다.
prev = [0] * (n + 1)
global_visited = [False] * (n + 1)

# prev를 기록하는 BFS
def bfs_with_prev(start, dest):
    prev[start] = start
    q = deque([(0, start)])

    while q:
        d, cur_node = q.popleft()
        # 목적지에 도달하면 최단 경로 리턴
        if cur_node == dest:
            return d

        for next_node in graph[cur_node]:
            # 직전 노드가 없으면 방문한다.
            # 그리고 prev에 직전 노드를 저장해둔다.
            if prev[next_node] == 0:
                prev[next_node] = cur_node
                q.append((d + 1, next_node))

    return -1

# 일반 BFS
# visited에는 S -> E로 이동할 때 사용된 노드들이 방문처리되어있다.
def bfs(start, dest, visited):
    q = deque([(0, start)])
    visited[start] = True

    while q:
        d, cur_node = q.popleft()
        if cur_node == dest:
            return d

        for next_node in graph[cur_node]:
            # 방문한 적이 없으면 방문한다.
            if not visited[next_node]:
                visited[next_node] = True
                q.append((d + 1, next_node))

    return -1

# S -> E까지의 경로 길이 및 prev 기록
answer = bfs_with_prev(s, e)

# 도착까지 최단 거리 + 사전순 경로에 방문 처리를 해준다.
cur = e
while prev[cur] != cur:
    global_visited[cur] = True
    cur = prev[cur]

# E -> S 경로 길이를 더하여 답을 출력한다.
print(answer + bfs(e, s, global_visited))