[백준 1260] DFS와 BFS

문제

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

 

입력

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

 

출력

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

---

접근

DFS와 BFS를 완벽히 이해하고 있었다고 생각했지만 문제를 풀어보니 아직 많이 부족하다.

특히 DFS를 스택으로 구현할 때 계속해서 틀렸다고 나와서 재귀로 접근을 했다. 그래서 정답이 되었는데 왜 스택은 틀린건지 아직 이해가가지 않았다. 다른 문제에서 DFS로 풀었을 때 너무 많은 재귀로 시간초과가 발생하기도 하였다.

DFS와 BFS의 원리와 코드를 더 완벽히 구현해야겠다.

 

구현

DFS를 구현한 함수이다.

노드를 전달받아 해당 노드에 방문표시를 하고 최종해에 추가하였다.

그리고 현재 노드와 연결된 노드를 찾았다면 해당 노드를 dfs함수에 전달하여 재귀를 시작한다.

def dfs(v):
    visited[v] = True
    dfs_list.append(v+1)

    for i in range(N):
        if graph[v][i] and not visited[i]:
            dfs(i)

 

BFS는 다음과 같이 큐로 구현하였다.

q는 deque()로 생성항였고 초기에 V-1을 대입하였다. 

그리고 해당 노드와 연결된 모든 노드를 큐에 넣고 넣은 순서대로 탐색을 진행한다.

while q:
    front = q.popleft()

    for i in range(N):
        if not visited[i] and graph[front][i]:
            q.append(i)
            bfs.append(i+1)
            visited[i] = True

---

전체 코드

from _collections import deque

def dfs(v):
    visited[v] = True
    dfs_list.append(v+1)

    for i in range(N):
        if graph[v][i] and not visited[i]:
            dfs(i)

N, M, V = map(int, input().split())
graph = [[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a][b] = graph[b][a] = 1

# dfs
dfs_list = []
visited = [False for _ in range(N)]
dfs(V-1)

# bfs
bfs = []
q = deque()
q.append(V-1)
bfs.append(V)
visited = [False for _ in range(N)]
visited[V-1] = True

while q:
    front = q.popleft()

    for i in range(N):
        if not visited[i] and graph[front][i]:
            q.append(i)
            bfs.append(i+1)
            visited[i] = True

print(*dfs_list)
print(*bfs)