백준 2644번 촌수계산(python)

from collections import deque

n=int(input())

p1, p2=map(int, input().split())

m=int(input())

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

for _ in range(m):

    사람1, 사람2=map(int, input().split())

    graph[사람1].append(사람2)

    graph[사람2].append(사람1)

def bfs(p1, p2, graph, n):

    visited=[-1]*(n+1)

    queue=deque()

    queue.append(p1)

    visited[p1]=0

    while queue:

        사람=queue.popleft()

        if 사람==p2:

            return visited[사람]

        for 이웃사람 in graph[사람]:

            if visited[이웃사람]==-1:

                visited[이웃사람]=visited[사람]+1

                queue.append(이웃사람)

    return -1

print(bfs(p1,p2,graph, n))

 

1. 입력으로 주어진 인접 리스트 그래프로 bfs

2. 시작에서부터 연결된 모든 노드 탐색> 방문 여부, 촌수 기록

3. end 찾으면 촌수 반환

4. 목표 노드 찾으면 이미 end 방문한거니까 촌수 증가 안시킴

 

왜 graph[a]=b, graph[b]=a 안쓰고 인접 리스트를 쓰는가?

단순 매핑이 아니고 그래프를 나타내야함. 그니까 1이랑 연결된게 2,3,4 이어야하니까