😊 백준 2644 : 촌수계산

2644: 촌수계산

DFS/BFS 세 번째 문제!
아직까진 dfs의 간단한 구현 문제라 어렵지 않다.

📌 Try 1

def dfs(start_node, cnt, visit = list()):
    visit.append(start_node)
    
    if start_node == d2:
        print(cnt)
        global check
        check = 1
    
    for x in graph[start_node]:
        if x not in visit:
            dfs(x, cnt+1, visit)

# input
people = int(input())
d1, d2 = map(int, input().split())

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

global check
check = 0

# output
dfs(d1, 0)

if check == 0:
    print(-1)

어려웠던 점은 예외 처리였다.
다른 방법이 떠오르지 않아, global 변수를 선언해서 처리했다.

🎯 다른 분 코드

from collections import deque
import sys

input = sys.stdin.readline
n = int(input())
a, b = map(int, input().split())
m = int(input())
s = [[] for i in range(n + 1)]
result = [0 for i in range(n + 1)]

def bfs(start):
    q = deque()
    q.append(start)
    visit = [0 for i in range(n + 1)]
    visit[start] = 1
    while q:
        d = q.popleft()
        for i in s[d]:
            if visit[i] == 0:
                visit[i] = 1
                result[i] = result[d] + 1
                q.append(i)
                
for i in range(m):
    x, y = map(int, input().split())
    s[x].append(y)
    s[y].append(x)
    
bfs(a)
print(result[b] if result[b] != 0 else -1)

double-list로 graph를 구성하셨다.

예외 처리 부분이 참신하다.
별도의 list로 처리하셨는데, 내가 잘 생각하지 못하는 방식이다.

🎁 Reference

• 깨지고 부서져라 - [백준] 2644번(python 파이썬)
  https://pacific-ocean.tistory.com/321