백준 2644 촌수계산 파이썬

백준 2644 촌수계산 풀이

접근방식

1. 큐 자료구조를 활용하여 노드 간의 관계 탐색하기
2. 거리가 0일 경우 해당하는 x의 거리에 1 더해주기

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

n = int(input())

# 타겟 1, 2
t1, t2 = map(int, input().split())

m = int(input())

# 관계 저장할 리스트 초기화
# n+1인 이유는 인덱스를 1부터 맞추기 위함
graph = [[] for _ in range(n+1)]

for _ in range(m):
    x, y = map(int, input().split())
    # x와 y에 양쪽 다 append 시켜서 서로 참조할 수 있도록 함
    graph[x].append(y)
    graph[y].append(x)

#print(graph)
# 거리를 모두 0으로 초기화
dist = [0 for _ in range(n+1)]

def bfs(start):
    # 큐 선언
    queue = deque()
    # 비어있는 큐에 start append
    # 함수 실행 시 start는 t1(문제에서 요구하는 타겟)
    queue.append(start)
    # 큐가 빌 때까지 실행
    while queue:
      # 이전에 넣은 start를 pop시키고 for문 실행
        x = queue.popleft()
      # print("x", x)
        for i in graph[x]:
          # 거리가 0이고 x와 연결될 경우 1 증가
          # 다시 i를 queue에 append
            if dist[i] == 0:
                dist[i] = dist[x] + 1
                # print("i", i,"dist", dist)
                queue.append(i)


bfs(t1)
# print("dist",dist)
print(dist[t2] if dist[t2] > 0 else -1)

bfs나 dfs문제를 풀 때 특히 실행 단계가 모호하거나

직관적으로 와닿지 않을 경우, 위에 주석 처리한 코드처럼

실제 변화되는 값들을 보면서 이해를 하고 있습니다.

주석 처리된 코드를 실행하면 결과는 다음과 같이 나옵니다.

입력 예시는 문제에서 주어진 것과 동일합니다.

graph [[], [2, 3], [1, 7, 8, 9], [1], [5, 6], [4], [4], [2], [2], [2]]
# 우리의 타겟은 7과 3의 관계입니다.
x 7
# for문 실행 시, graph[7] = 2입니다.
i 2 dist [0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
# 이전에 사용된 2가 x자리로 갑니다
# 그러면 for i in graph[2] 이기 때문에 i에는 1, 7, 8, 9가 들어갑니다.
x 2
i 1 dist [0, 2, 1, 0, 0, 0, 0, 0, 0, 0]
i 7 dist [0, 2, 1, 0, 0, 0, 0, 2, 0, 0]
i 8 dist [0, 2, 1, 0, 0, 0, 0, 2, 2, 0]
i 9 dist [0, 2, 1, 0, 0, 0, 0, 2, 2, 2]
# i가 1일 경우 다시 x로 가게 되고 graph[1]은 2와 3을 가지고 있지만 
# dist[2]는 0이 아니기 때문에 pass 됩니다.
x 1
i 3 dist [0, 2, 1, 3, 0, 0, 0, 2, 2, 2]
x 7
x 8
x 9
x 3
dist [0, 2, 1, 3, 0, 0, 0, 2, 2, 2]

촌수계산 문제는 dfs 또는 bfs로 풀 수 있어서 답안 예시가 다양합니다.

실버 2 수준의 문제였지만 queue 자료구조나 bfs(너비우선탐색) 알고리즘 연습에

좋은 문제라고 생각헙니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady