백준/ Silver 2 문제 , 백준 파이썬 2644, 촌수계산 [BFS]

백준/ Silver 2 문제 , 백준 파이썬 2644, 촌수계산 [BFS]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
이전 1389 문제랑 똑같이 접근

 

문제 출처

 

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

2644번: 촌수계산

 

접근법

 

 

https://bmy1320.tistory.com/entry/%EB%B0%B1%EC%A4%80-Silver-1-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-1389-%EC%BC%80%EB%B9%88-%EB%B2%A0%EC%9D%B4%EC%BB%A8%EC%9D%98-6%EB%8B%A8%EA%B3%84-%EB%B2%95%EC%B9%99-BFS

백준/ Silver 1 문제 , 백준 파이썬 1389, 케빈 베이컨의 6단계 법칙 [BFS]

 

위의 케빈 베이컨 문제와 거의 같은 풀이로 풀렸다.

 

촌수를 확인할  두 숫자를 전달한 뒤 bfs를 돌려 완성된 배열에 두숫자의 자릿수에 맞는 숫자를 출력시켜주면 된다.

 

 

 

 

 

 

정답

 

 

 

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

def bfs(graph,X,Y):
    course=[0]*(N+1)
    dq=deque()
    dq.append(X)
    check=[X]
    while dq:
        X=dq.popleft()
        for j in graph[X]:
            if j not in check:
                course[j]=course[X]+1
                check.append(j)
                dq.append(j)
    result=course[Y]
    if result==0:
        return -1
    else:
        return result

N=int(input())
a,b=map(int,input().split())
graph=[[] for _ in range(N+1)]
for _ in range(int(input())):
    x,y=map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

print(bfs(graph,a,b))