[백준 | 파이썬] 1260 : DFS와 BFS

💡 가장 기본이 되는 DFS, BFS 문제!

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

풀이 방법

우선 그래프를 표현해야 한다.

우선 그래프를 표현하기 위해 0부터 n까지의 인덱스를 가지도록 n+1 길이의 배열을 만든다. 배열의 각 원소는 빈 리스트가 주어지도록 한다. 인덱스는 각각 부모 노드를 의미하고, 원소는 각 부모 노드의 원소를 의미한다.

노드들은 서로 연결되어 있으므로 서로가 서로의 자식이자 부모이다. a, b 가 입력되면 graph[a].append(b) graph[b].append(a)를 해 주어서 각각의 노드가 자식 노드를 가질 수 있도록 해 준다.

방문한 노드를 표시하기 위해 n+1 길이의 배열을 준비한다. 배열의 원소는 False 이고, 노드를 방문했을 때 해당 인덱스의 값을 True 로 바꿔준다.

1. DFS

재귀를 활용해 푼다.

시작 노드에 우선 방문 처리를 한 뒤, 시작 노드의 자식 노드들을 돌면서 방문 처리가 되지 않은 노드인 경우에만 재귀 함수를 실행한다.

방문 처리가 되어있다면 그 다음 원소에 대해 반복해서 탐색한다. 재귀를 수행하는 조건을 방문 처리로 걸어주었기 때문에 모든 노드를 방문하고 나면 함수가 종료된다.

1. BFS

큐를 활용해서 푼다. 큐는 다음에 방문할 노드들의 대기열이라고 보면 된다.

큐에 시작 노드를 추가한 다음 방문 처리를 해 준다. 큐에서 첫 번째 노드를 뽑아 출력하고, 시작 노드의 자식 노드들을 돌면서 방문 처리가 되지 않은 노드인 경우에만 큐에 노드를 넣어주고, 방문 처리를 해 준다.

큐에 있는 노드들이 모두 출력될 때까지 = 모든 노드를 방문할 때까지 반복문을 수행한다.

# DFS 와 BFS
from collections import deque

n, m, v = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False]*(n+1)

def dfs(node):
    print(node, end=' ')
    visited[node] = True
    for i in sorted(graph[node]):
        if not visited[i]:
            dfs(i)

def bfs(node):
    queue = deque()
    queue.append(node)
    visited[node] = True
    while queue:
        nd = queue.popleft()
        print(nd, end=' ')
        for i in sorted(graph[nd]):
            if not visited[i]:
                queue.append(i)
                visited[i] = True

dfs(v)
print()
visited = [False]*(n+1)
bfs(v)