[python] 백준 2644번 촌수계산

백준 2644번 촌수계산

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

문제

풀이

이게 과연 bfs 일까, dfs 일까로 시간 진짜 많이 썼는데 결국 다 된다는 걸 깨달은 나. 덕분에 둘 다 복습했다. 럭키비키잖아? ^^

import sys
sys.setrecursionlimit(10*6)

n = int(input())
v, parent = map(int, input().split())
m = int(input())
edgelist = []
for _ in range(m):
    edgelist.append(list(map(int, input().split())))

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

for v1, v2 in edgelist:
    graph[v1].append(v2)
    graph[v2].append(v1)

일단 주어진 입력값이 간선리스트라 그래프로 바꿔줬다.

BFS

개인적으로 bfs가 먼저 떠올랐다. 최솟값 count를 구하는 거와 비슷했기 때문.

from collections import deque

def bfs(v):
    visited = [False] * (n+1)
    visited[v] = True
    queue = deque([(v, 1)])
    while queue:
        v, count = queue.popleft()

        for i in graph[v]:
            if i == parent: 
                print(count)
                return True
            
            if not visited[i]:
                visited[i] = True
                queue.append((i, count+1))


if not bfs(v):
    print(-1)

그리고 bfs 가 더 구현하기 쉬웠다. count 를 어디에 넣어야하지 고민도 안해도 되고, return True 한 번이면 재귀함수가 아니기에 바로 돌아와서, if not bfs(v)도 아주 잘 동작했기 때문.

DFS

import sys
sys.setrecursionlimit(10*6)

visited = [False] * (n+1)

def dfs(visited, v, count):
    visited[v] = True
    count += 1

    for i in graph[v]: 
        if i == parent: 
            print(count)
            return True

        if not visited[i]:
            if dfs(visited, i, count):  # 재귀 호출의 결과를 확인하여 부모 노드를 찾으면 탐색 종료
                return True

    return False

if not dfs(visited, v, 0):
    print(-1)

반면 dfs, 일단 count 를 저렇게 놔도 되나? 긴가민가했다. 알고보니 저렇게 count 를 두면, 동일한 깊이에 있는 노드들은 동일한 카운트를 갖더라!

그리고 또 하나의 문제,처음에는 if not visited[i]: dfs(visited, i, count) 라고만 적었는데, 그랬더니 count 랑 -1 이랑 동시에 떴다. 알고봤더니, DFS가 한 경로에서 부모 노드를 찾았다고 하더라도 상위 호출로 돌아갈 때, 다른 경로를 탐색하게 되면 결과가 왜곡되더라. 그래서 만약 dfs(visited, i, count)가 참일 때, 모든 탐색을 중단하고 돌아가게끔 추가해줘야 한다.

📌 주의

• dfs/bfs 기본기를 잘 다지자.