백준: 1260 DFS와 BFS

문제

1260번: DFS와 BFS

 

문제 풀이

 그래프에 대한 정보가 주어질 때, DFS(Depth - First - Search)와 BFS(Breadth - First - Searh)를 통해 탐색할 경우에 탐색 순서를 결과로 반환하는 문제이다. 따라서 문제를 풀기 위해서는 DFS와 BFS에 대해 이해하고 있어야 한다.

 

DFS 구현

def dfs(depth, cur_node, visited):
    # 이미 시작 지점은 방문하였으므로, 탐색 경로는 n - 1
    if depth == n - 1:
        return

    for next_node in range(n):
        if graph[cur_node][next_node] and next_node + 1 not in visited:
            visited.append(next_node + 1)
            dfs(depth + 1, next_node, visited)
    return visited

 DFS는 재귀 호출이나 Stack으로 구현할 수 있다. Stack으로 구현한다면, 특정 노드에서 접근 가능한 다른 노드들을 역순으로 삽입하여야 한다. 따라서 재귀 호출도 Stack과 같은 원리 이므로 이를 통해 DFS를 구현하였다. depth가 의미하는 것은 방문 가능한 노드들을 다 방문하였는지 확인하기 위함이다.

 또한 순열, 조합과 달리 재귀 호출을 하더라도 백트랙킹을 할 필요가 없기에 한 번 방문한 노드를 다시 해제할 필요가 없다. 만약 방문 가능한 모든 경로를 구하라고 한다면, 백트랙킹을 위해 재귀 호출 후에 visited.pop()이 필요하다.

 

BFS 구현

def bfs(start):
    # 시작 지점 추가와, 방문 표시
    q = deque([start])
    visited = [start + 1]

    while q:
        cur_node = q.popleft()
        for next_node in range(n):
            if graph[cur_node][next_node] and next_node + 1 not in visited:
                q.append(next_node)
                visited.append(next_node + 1)
    return visited

 BFS는 DFS와 달리 Queue로 구현할 수 있다. 먼저 탐색한 노드를 우선적으로 처리함으로써 depth로 뻗어가는 것이 나닌 Breadth로 뻗어 갈 수 있다.

 

코드

from collections import deque


def bfs(start):
    # 시작 지점 추가와, 방문 표시
    q = deque([start])
    visited = [start + 1]

    while q:
        cur_node = q.popleft()
        for next_node in range(n):
            if graph[cur_node][next_node] and next_node + 1 not in visited:
                q.append(next_node)
                visited.append(next_node + 1)
    return visited


def dfs(depth, cur_node, visited):
    # 이미 시작 지점은 방문하였으므로, 탐색 경로는 n - 1
    if depth == n - 1:
        return

    for next_node in range(n):
        if graph[cur_node][next_node] and next_node + 1 not in visited:
            visited.append(next_node + 1)
            dfs(depth + 1, next_node, visited)
    return visited


if __name__ == "__main__":
    n, m, v = map(int, input().split())
    graph = [[False] * n for _ in range(n)]

    for _ in range(m):
        i, j = map(int, input().split())
        # 그래프는 양방향이므로 반전하여 체크해줘야 함
        graph[i - 1][j - 1] = True
        graph[j - 1][i - 1] = True

    print(*dfs(0, v - 1, [v]))
    print(*bfs(v - 1))