[BOJ] 2644. 촌수 계산

문제

촌수계산 (https://www.acmicpc.net/problem/2644)

풀이

1. 초기 접근

• 문제조건 해석
  • 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다.
    • BFS 문제다.
• 알고리즘
  • 가장 기초적인 BFS 문제라고 생각된다.
  • 파이썬에서 그래프 탐색이 필요한 문제들은, 일단
    • dict {} 로 그래프를 먼저 만들고, (부모노드가 key, 자식노드들이 해당 key의 values가 된다.)
    • set {} 으로 방문체크용 스트럭처를 만들면 된다.
    • 이러면 노드접근에 모두 상수시간 O(1) 밖에 안걸린다.
• 코드

import sys
from collections import defaultdict

n = int(input())
a, b = map(int, input().split())
t = int(input())

d = defaultdict(set)

for _ in range(t):
    x, y = map(int, input().split())
    d[x].add(y)
    d[y].add(x)

def bfs(a, b):
    q, visited = [a], {a}
    step = 0
    while q:
        size = len(q)

        for i in range(size):
            cur = q.pop(0)
            if cur == b:
                return step

            for j in d[cur]:
                if j not in visited:
                    visited.add(j)
                    q.append(j)

        step += 1
    return -1

print(bfs(a, b))