[python 파이썬] 백준 2644번 촌수계산

www.acmicpc.net/problem/2644

2644번: 촌수계산

처음에 이 문제를 봤을 때 트리구조를 생각했다. 트리구조로 푸려고 하니 도저히 아이디어가 안떠올랐다. 

 

찾아보니 이 문제는 시작지점부터 목표지점까지 몇번 거쳐야하는지 생각하는 단순 탐색 문제였다. 

bfs로 입력받은 값 기준으로 시작해서 연결되어있는 곳을 찾아 +1씩 더해나가면 문제를 풀 수 있다. 

 

이 문제에서는 인접리스트를 적용하여 풀었다. 

from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
a, b = map(int, input().split())
m = int(input())
adj = [[] for i in range(n + 1)]
result = [0 for i in range(n + 1)]
def bfs(start):
    q = deque()
    q.append(start)
    visit = [0 for i in range(n + 1)]
    visit[start] = 1
    while q:
        d = q.popleft()
        for i in adj[d]:
            if visit[i] == 0:
                visit[i] = 1
                result[i] = result[d] + 1
                q.append(i)
for i in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)
bfs(a)
print(result[b] if result[b] != 0 else -1)

 

[참고]

pacific-ocean.tistory.com/321