[백준 2644번] 촌수계산

박형진·2022년 8월 15일
0

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


1. BFS 풀이

""" BFS """
import sys
from collections import defaultdict, deque

graph = defaultdict(list)
distance = defaultdict(lambda: -1)
n = int(sys.stdin.readline().rstrip())
a, b = map(int, sys.stdin.readline().rstrip().split())
for _ in range(int(sys.stdin.readline().rstrip())):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    graph[x].append(y)
    graph[y].append(x)

q = deque([a])
distance[a] = 0

while q:
    v = q.popleft()
    for u in graph[v]:
        if distance[u] == -1:
            distance[u] = distance[v] + 1
            q.append(u)
print(distance[b])

2. DFS 풀이

""" DFS """
import sys
from collections import defaultdict

graph = defaultdict(list)
visited = defaultdict(bool)
n = int(sys.stdin.readline().rstrip())
start, dest = map(int, sys.stdin.readline().rstrip().split())
for _ in range(int(sys.stdin.readline().rstrip())):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    graph[x].append(y)
    graph[y].append(x)

ans = [-1]


def dfs(node, distance):
    if node == dest:
        ans[0] = distance
        return None

    for u in graph[node]:
        if not visited[u]:
            visited[u] = True
            dfs(u, distance + 1)
            visited[u] = False


visited[start] = True
dfs(start, 0)
print(ans[0])

딱 DFS와 BFS의 개념을 공부할 때 좋은 문제라고 생각한다.
DFS의 경우 함수의 파라미터로 path를 추가하여 not in path방식으로 변경할 수 있다.

profile
안녕하세요!

0개의 댓글