[백준 2644] 촌수계산

1. 문제

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

2644번: 촌수계산

2. 접근 방법

bfs로 접근하면 됩니다요

visit확인 필수 ..

 

처음에 visit 확인하는 부분을 잘 못 넣었다가 메모리 초과가 나버렸습니다.

넘 당황해서 서치해봤더니 똑같은 부분에서 문제가 ..^^

(참고 https://hqjang.tistory.com/97)

3. 코드

python

from collections import deque

N = int(input())
S, G = map(int, input().split())
M = int(input())
connections = [[] for _ in range(N+1)]
for _ in range(M):
    x, y = map(int, input().split())
    connections[x].append(y)
    connections[y].append(x)

visited = [False] * (N+1)
is_answer = False
q = deque()
q.append((S, 0))

while q:
    now, cnt = q.popleft()
    if now == G:
        is_answer = True
        print(cnt)
        break
    else:
        if not visited[now]:
            for _next in connections[now]:
                q.append((_next, cnt+1))
            visited[now] = True

if not is_answer:
    print(-1)

4. 마치며

ㅁㅏ치며!~