2644 : 촌수계산

1062 단어 백준파이썬백준

문제

코드

from collections import deque

n = int(input())
num1,num2 = map(int,input().split())
m = int(input())

def bfs(num1):
    queue = deque()
    queue.append(num1)
    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if chonesoo[i] == 0 :
                chonesoo[i] = chonesoo[x]+1 
                queue.append(i)

    

graph = [[] for _ in range(n+1)]
chonesoo = [0 for _ in range(n+1)]

for _ in range(m):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

bfs(num1)
print(chonesoo[num2] if chonesoo[num2]!=0 else -1)

해설

전형적인 DFS BFS문제인데 다른 점이 있다면 완전 전형적이라는 것이다.
다른 문제 같은경우 행렬의 방식으로 접근을 하지만
이 문제는 그래프로 노드끼리 간선을 연결해주는것을 입력받아서 해주는 방식인것이다.
그리고 노드끼리 얼마나 멀리 떨어져있는지 정도가 촌수라고 보면 된다.

그래서 그래프 리스트와 촌수리스트를 생성해주고
그래프 리스트에는 노드들을 연결시켜주고 num1로부터 얼마나 떨어져있는지 chonesoo 리스트에 저장하는 방식으로 문제를 해결했다.

좋은 웹페이지 즐겨찾기