[Python/파이썬] 백준 22868번 산책 (small)

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

코드

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
for i in range(1, n+1):
    graph[i].sort()
s, e = map(int, input().split())


def bfs(excludes):
    q = deque([[s]])
    visited = [False]*(n+1)
    for ex in excludes:
        visited[ex] = True
    visited[s] = True
    while q:
        now_path = q.popleft()
        for nx in graph[now_path[-1]]:
            if not visited[nx]:
                if nx == e:
                    return now_path
                q.append(now_path+[nx])
                visited[nx] = True


# S -> E
se_path = bfs([])
# E -> S
es_path = bfs(se_path[1:])
print(len(se_path)+len(es_path))

 

한 점에서 다른 한 정점으로 가는 최단 경로를 두 번 찾으면 되는 문제다. 여기서는 경로가 양방향이고, 모두 길이가 1이기 때문에 복잡하게 생각할 필요 없다. 그냥 S->E로 가는 최단 경로를 찾아놓고, 남은 정점들로 E->S로 가는 최단 경로를 찾으면 된다. 

그래서 인자로 받은 점들은 제외하고 경로를 찾는 BFS 함수를 구현했다. 처음에는 인자로 빈 배열을 줘서 모든 정점에 대해 S->E로 가는 최단 경로를 찾도록 하고, 그 다음에는 S->E로 가는 최단 경로에 쓰인 정점들의 배열을 인자로 주고 BFS를 실행하여 E->S로 돌아오는 최단 경로를 구한다. 이때 설명에서는 명확하게 하려고 E->S로 돌아오는 길을 구한다고 했지만, 앞서 말했듯이 길은 양방향이고 모두 길이가 같기 때문에 S->E로 구해도 똑같기 때문에 코드에서도 굳이 구분하지 않았다.