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

🥚문제

---

🥚입력/출력

---

🍳코드

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

n = int(input().strip())
x, y = map(int, input().split())
m = int(input().strip())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    parent, child = map(int, input().split())
    # 양방향 그래프로 설정해준다
    graph[parent].append(child)
    graph[child].append(parent)


# distance[v] = v까지의 거리
# -1 = 방문하지 않음
distance = [-1]*(n+1)

def bfs(node):
    # node와 연결된 모든 노드들의 거리를 구한다
    q = deque([])
    q.append(node)
    distance[node] = 0

    while q:
        node = q.popleft()
        for new_node in graph[node]:
            # 방문하지 않았다면
            if distance[new_node] == -1:
                q.append(new_node)
                # 이전 노드까지의 거리 + 1
                distance[new_node] = distance[node]+1


# 촌수를 계산하고자 하는 사람 x와 연결된 다른 노드들의 거리를 구한다
# 결과로 얻어진 distance[y]를 출력하면 x와 y의 거리를 알 수 있다
bfs(x)
print(distance[y])

---

🧂아이디어

탐색

• 입력을 가중치가 없는 양방향 그래프로 볼 수 있다. 이를 인접 리스트로 표현한다.
• 촌수는 노드사이의 최소 거리 = 간선의 최소 개수이다.
• BFS를 통해서 풀이했다.
• def bfs(node)
  • bfs로 노드 node와 연결된 모든 노드들간의 최소 거리를 구한다.
  • 이때 계산한 거리는 리스트 distance에 저장해준다.
  • node에서 new_node로 갈 수 있으면 distance[new_node] = distance[node] + 1
  • 즉, dfs(node) 실행을 마친 후 갱신된 리스트 distance의 distance[some_node]는 node에서 some_node로의 촌수(최소 거리)를 나타낸다.
  • 친척 관계가 없으면 (= 경로가 없으면, 방문한 적이 없으면) distance[some_node] = -1