[ BOJ 2644 ] 촌수계산(Python)

문제

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

문제를 트리 형태로 생각해서 더 어렵게 접근하려고 했다.
그냥 bfs 문제와 동일하게 풀면 된다!

문제 풀이

1. 그래프를 2차원 배열로 만들고, 각각의 인덱스에 연결된 사람을 추가해준다.
   (ex. 1번째 인덱스엔 1번 사람과 연결된 사람들을 추가해준다.)
2. 먼저 queue에 (q1,cnt)를 넣어준다. q1, q2는 촌수를 구해야 할 두 사람이다.
3. queue에서 v,cnt를 pop해준다. 해당 사람 v를 방문 안했으면, cnt에 1을 더해주고, 방문했다고 체크해준다.
4. 해당 사람 v와 연결된 다른 사람들(graph[v]) 중 방문 안한 사람이 있으면 queue에 (graph[v],cnt+1) 를 추가해준다.
5. 만약 v가 q2와 같으면 cnt를 리턴한다. 하지만 queue를 모두 확인했는데 같지 않다면 -1을 리턴한다.

코드

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

def bfs(v, target):
    #queue에 정점과 cnt를 넣어줌
    queue = deque([[v,0]])

    while queue:
        temp = queue.popleft()
        v = temp[0]
        cnt = temp[1]

        #정점이 target과 같으면 cnt 반환
        if v == target:
            return cnt

        #방문 안한 정점이면 방문해준다.
        if not visited[v]:
            visited[v] = True
            #해당 정점과 연결된 정점들 중에 방문 안한 정점이 있으면 queue에 추가
            for i in graph[v]:
                if not visited[i]:
                    queue.append([i,cnt+1])
    # 해당 정점과 연결된 모든 정점을 확인 했는데 target을 찾지 못했으면
    # 연결되지 않았으므로 촌수를 계산할 수 없음
    return -1

#전체 사람의 수 n, 우리가 촌수를 구해야 하는 사람 q1, q2
n = int(input().rstrip())
q1, q2 = map(int,input().rstrip().rsplit())
m = int(input().rstrip())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

#부모 자식간의 관계 개수 m
for _ in range(m):
    #x가 y의 부모
    x, y = map(int,input().rstrip().rsplit())

    #양방향으로 그래프에 추가해줌
    graph[x].append(y)
    graph[y].append(x)

print(bfs(q1,q2))