[백준/파이썬] 2644번

📍백준 2644번 문제

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

코드

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

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

que = deque()
que.append(a)
visited[a] = 0
flag = False
while que:
    node = que.popleft()
    if node == b:
        print(visited[b])
        flag = True
        break
    for next in graph[node]:
        if visited[next] == -1:
            visited[next] = visited[node] + 1
            que.append(next)
if flag == False:
    print(-1)

풀이

• 양방향 그래프 이므로 값을 입력받으면 graph[i], graph[j]에 모두 각각의 값을 추가해준다.
• BFS를 이용해 문제를 풀었다.
• 부모자식 관계가 아닐 때 -1을 출력해야 하므로 flag를 이용했다.