99클럽 코테 스터디 17일차 TIL + DFS/BFS

[오늘의 학습 키워드 및 문제]
- 백준의 "촌수계산" 문제를 풀었다.
- 너비 우선 탐색과 깊이 우선 탐색 두 방식으로 모두 풀어볼 수 있다.

[나의 코드]

# DFS 풀이

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

graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)
result = []

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    
def dfs(v, count):
    count += 1
    visited[v] = True
    
    if v == b:
        result.append(count)
    
    for i in graph[v]:
        if not visited[i]:
            dfs(i, count)

dfs(a, 0)

if len(result) == 0:
    print(-1)
else:
    print(result[0] - 1)

깊이 우선 방식으로 풀어보았다.
문제를 읽어보면 느낌적으로 이건 깊이 우선 방식으로 푸는 게 더 낫다는 생각이 든다.

 

# BFS 풀이

from collections import deque
 
n = int(input())
a, b = map(int, input().split())
m = int(input())

graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    
def bfs(v):
    q = deque([v])
    visited[v] = 0
    
    while q:
        now = q.popleft()
        
        for i in graph[now]:
            if visited[i] == 0:
                visited[i] = visited[now] + 1
                q.append(i)

bfs(a)

if visited[b]:
    print(visited[b])
else:
    print(-1)

너비 우선 방식(BFS)으로도 풀어보았다.
너비 우선 방식은 큐를 이용한다. 정확히는 덱이다.

[오늘의 회고]
- 오늘 배탈 나서 풀 기분이 안 든다. 대충 풀고 내일 복습 한 번 더 하련다.
- BFS와 DFS는 그냥 코드를 외우는 게 좋다. 근데 나는 BFS가 훨씬 편하다. 재귀는 어려우니까. 끝!