[백준] 1260번 - DFS와 BFS (Python3)

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

문제

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

입력

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

출력

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

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1

1 2 4 3
1 2 3 4

예제 입력 2

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2

3 1 2 5 4
3 1 4 2 5

예제 입력 3

1000 1 1000
999 1000

예제 출력 3

1000 999
1000 999

 

 

 

내 풀이

예제 1번과 2번에 대한 그림을 그려 보았다.

예제1

예제2

DFS는 시작점에서부터 갈 수 있는 길을 모두 따라가며 끝장을 보고 오는 형식

BFS는 시작점에서부터 한 단계씩 다음 레벨의 노드들을 차례로 탐색하는 형식

이라고 생각하면 될 것 같다.

 

이를 바탕으로 작성한 코드다.

import sys
import collections

def dfs(node):
    visited[node] = 1   # 노드 방문 표시
    print(node, end=' ')
    for i in lines[node]:   # 현재 노드와 연결된 노드들 불러오기 (작은 수부터 탐색해야 하기 때문에 정렬 필요)
        if visited[i] == 0: # 아직 방문하지 않은 노드라면 재귀함수 호출
            dfs(i)  # 재귀함수호출
        else:
            continue
    return

def bfs(node):
    dq = collections.deque()
    dq.append(node)
    visited[node] = 1
    while dq:
        done = dq.popleft()
        print(done, end=' ')
        for i in lines[done]:
            if visited[i] == 0:
                dq.append(i)
                visited[i] = 1
    return


N, M, V = map(int, sys.stdin.readline().split())
lines = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, sys.stdin.readline().split())
    lines[a].append(b)
    lines[b].append(a)
for row in lines:
    row = row.sort()    # 작은 수부터 탐색하기 위해 정렬해줌

visited = [0 for i in range(N+1)]   # 인덱스 맞추기 위해 의미 없는 칸 1개 있음 (0번 인덱스)
dfs(V)
print()
visited = [0 for i in range(N+1)]
bfs(V)

DFS와 BFS를 사용할 경우 모두 해당 노드를 방문했는지를 표시할 수 있는 visited 배열이 필요하다. 인덱스를 노드 번호와 맞추기 위해 0번 인덱스를 의미 없는 칸으로  두었다.

 

처음에 연결 관계를 입력할 때, 쌍방향 연결이므로 각 노드마다 연결된 노드들이 들어 있는 리스트 lines를 만들어주었다. lines 또한 노드와 인덱스를 맞춰주기 위해 실제 노드의 개수보다 length가 1 더 길다.

문제의 조건 중 한 노드에서 다음 노드를 탐색할 때, 작은 수의 노드부터 탐색한다는 것이 있었으므로 정렬을 수행해주었다.

 

dfs를 하게 되면 우선 현재 노드에 방문 표시를 해 주고, 그 노드와 연결된 노드들을 살펴보고 방문하지 않은 노드가 있다면 그 노드에 대한 재귀함수를 호출해준다.

 

bfs를 하게 될 경우에는 큐(Queue) 자료구조를 사용하는 것이 좋다. 이를 위해 collections 모듈의 deque를 사용해준다.

먼저 현재 노드를 deque에 넣어주고그 노드를 방문처리 해준다. 그 이후 가장 먼저 들어온 노드를 popleft 해주고, 그 노드와 연결된 노드들을 탐색하고 방문하지 않았다면 deque에 넣어준다. 이를 deque가 비어 있을 때까지 반복한다.