[백준] 2644 촌수계산 (실버2) / DFS, BFS (feat. 파이썬튜터)

문제요약

나의 코드 및 설명 01 - DFS

def dfs(s, count, temp_list): #방문한 노드를 temp_list에 담는다
    global ans
    if end in temp_list:
        ans = count
        return #리턴필수! 그래야 더 이상 다음 노드 안 담음!
    for i in graph[s]:
        if i not in temp_list: #temp_list에 i가 안 담겨 있다면
            dfs(i, count+1, temp_list+[i])

n = int(input())
start, end = map(int, input().split())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

ans = -1

dfs(start, 0, [start]) #초기 temp_list에는 시작 노드가 담겨있어야 한다
print(ans)

나의 코드 및 설명 02 - BFS

from collections import deque

def bfs(s,e):
    queue = deque()
    queue.append(s)
    visited[s] = 1
    while queue:
        node = queue.popleft()
        if node == e:
            return visited[node]-1
        for i in graph[node]:
            if visited[i] == 0:
                visited[i] = visited[node] + 1
                queue.append(i)
    return -1 #이게 실행된다면 촌수를 계산할 수 없는 거임

n = int(input())
start, end = map(int, input().split())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
visited = [0]*(n+1)

print(bfs(start,end))

 

피드백

DFS와 BFS으로 풀어본 문제. 처음엔 시작 노드에서 목표 노드까지 깊게 탐색하는 식으로 문제를 풀면 될 것이라고 생각했고, 실제로 그렇게 풀어서 맞았다. DFS 함수 변수에 방문한 노드들을 담을 temp_list를 선언했고, temp_list에 목표 노드가 담겨있다면, ans를 count 변수 값으로 갱신하는 코드를 작성했는데, 주의할 점은 return 해주어야 한다는 것이다. 리턴을 해주지 않으면 계속해서 다음 노드를 담을 수 있고, ans 값이 1씩 증가하게 될 것이다! (파이썬 튜터를 통해 이해했다.) 

BFS으로도 풀어봤는데, 이 문제는 DFS, BFS 모두 적합한 문제인 것 같다.

temp_list의 마지막 요소에 3이 담겼을 때 꼭 리턴해주어야 한다!