[백준] 2644 촌수계산 python

www.acmicpc.net/problem/2644

2644번: 촌수계산

import sys
input = sys.stdin.readline

from collections import deque
N = int(input())
s, e = map(int, input().split())
link_arr = [list() for _ in range(N + 1)]
M = int(input())
for _ in range(M):
    n1, n2 = map(int, input().split())
    link_arr[n1].append(n2)
    link_arr[n2].append(n1)

visit = [-1] * (N + 1)
q = deque()
q.append(s)
visit[s] = 0
while q:
    cur = q.popleft()
    if cur == e:
        break
    for adj in link_arr[cur]:
        if visit[adj] > -1: continue
        visit[adj] = visit[cur] + 1
        q.append(adj)

print(visit[e])

그래프 탐색을 해서 풀수있는 문제이다

BFS 를 사용해서 최소거리를 구하는 방식으로 구현했다

기본적인 코드에 현재 방문한 노드가 도착하는 노드인 경우에 break를 걸어서 반복문을 끝나게 했다.

 

이정도는 easy~