""" BFS """
import sys
from collections import defaultdict, deque
graph = defaultdict(list)
distance = defaultdict(lambda: -1)
n = int(sys.stdin.readline().rstrip())
a, b = map(int, sys.stdin.readline().rstrip().split())
for _ in range(int(sys.stdin.readline().rstrip())):
x, y = map(int, sys.stdin.readline().rstrip().split())
graph[x].append(y)
graph[y].append(x)
q = deque([a])
distance[a] = 0
while q:
v = q.popleft()
for u in graph[v]:
if distance[u] == -1:
distance[u] = distance[v] + 1
q.append(u)
print(distance[b])
""" DFS """
import sys
from collections import defaultdict
graph = defaultdict(list)
visited = defaultdict(bool)
n = int(sys.stdin.readline().rstrip())
start, dest = map(int, sys.stdin.readline().rstrip().split())
for _ in range(int(sys.stdin.readline().rstrip())):
x, y = map(int, sys.stdin.readline().rstrip().split())
graph[x].append(y)
graph[y].append(x)
ans = [-1]
def dfs(node, distance):
if node == dest:
ans[0] = distance
return None
for u in graph[node]:
if not visited[u]:
visited[u] = True
dfs(u, distance + 1)
visited[u] = False
visited[start] = True
dfs(start, 0)
print(ans[0])
딱 DFS와 BFS의 개념을 공부할 때 좋은 문제라고 생각한다.
DFS의 경우 함수의 파라미터로 path를 추가하여 not in path방식으로 변경할 수 있다.