[백준 파이썬] #2644. 촌수계산

풀기 전 생각해보기😮

• 트리 그래프 그리기, 방문 여부를 체크해주는 것으로 풀이가 가능
• 양방향 간선 vs 단방향 간선 연결관계 중 어떤 것을 선택해야 할까
• BFS 풀이로 접근해보자

---

풀이🛫

구글링 참고

# 트리 구조를 그리고 visited 여부 체크
# 시작하는 노드로부터 부모, 자식에 관계없이 촌수를 체크할 수 있다 -> visited는 비교 노드간 거리가 됨

from collections import deque

def bfs(node):
    queue = deque()     # 덱 생성
    queue.append(node)  # 덱에 노드 정보 입력
    while queue:        # 큐가 살아있는 동안
        node = queue.popleft()      # 노트에서 하나의 요소를 빼서
        for i in graph[node]:       # 연결된 노드들에 대해 검사 진행
            if visited[i] == 0:         # 아직 검사되지 않은 노드일 때
                visited[i] = visited[node] + 1      # 기준이 되는 노드의 방문 기록 + 1
                queue.append(i)     # 방문 중인 노드를 큐에 삽입 -> bfs 진행


N = int(input())
a, b = map(int, input().split())
M = int(input())
graph = [[] for _ in range(N+1)]
visited = [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(a)

if visited[b] > 0:      # x에서 시작한 bfs를 통해 y를 방문할 수 있다면
    print(visited[b])       # y까지의 촌수를 출력
else:                   # 그렇지 못할 경우
    print(-1)               # -1을 출력

 

핵심 정리🎁

graph[x].append(y)
graph[y].append(x)

• 왜 양방향으로 진행되어야 하는 지 잘 이해하지 못했었다. 양방향으로 연결정보를 모두 담았을 때, 부모자식에 관계없이 노드로부터 거리를 표시할 수 있다.
• bfs(node)에서 node값이 어떤 트리 구조의 중간 노드라고 하더라도, node를 중심으로 부모, 자식에 관계 없이 뻗어나가기 때문에, node가 루트 노드인 그래프를 두고 탐색할 때와 동일한 기능이 이뤄진다. 

 

링크💎

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

2644번: 촌수계산

 

후기 😎

• 트리구조를 중점적으로 공부해보자
• 양방향 관계, 단방향 관계를 파악할 수 있어야 한다