백준 온라인 저널, DFS, BFS/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번째 줄부터 간선으로 연결된 정점 2개만 출력하므로 v를 찾아 연결된 그래프를 모두 출력하기에는 다소 코드가 복잡해진다. 따라서 이를 정점을 인덱스로 갖고, 그 정점과 연결되어있는 정점을 값으로 갖는 리스트로 변환해준다.

 

접근 방법

1. 주어진 간선에 대한 정보를 정점을 인덱스로 갖고, 그 정점과 연결되어있는 정점을 값으로 갖는 리스트(map_)로 변환시켜주고 방문처리를 위한 정점의 개수만큼의 길이를 갖는 리스트(visited)를 형성한다.

 

2. dfs는 시작지점(v)을 기준으로 방문처리를 해준 뒤, 오름차순으로 정렬되어있는 map_에 있는 원소(v와 연결된 정점)를 하나씩 뽑아서 방문처리가 안된 원소에 대해 재귀적으로 작동하도록 한다.

 

3. bfs는 시작지점(v)을 기준으로 방문처리를 해준뒤 원소를 queue에 삽입하고 이를 꺼낸다. 그리고 오름차순으로 정렬되어있는 map_에 있는 원소(v와 연결된 정점)를 하나씩 뽑아서 queue에 삽입한다. 모두 꺼내면 queue에서 원소를 하나 뽑아서 위의 과정을 반복한다.

 

 

 

코드

import sys
from collections import deque
n, m, v = map(int, sys.stdin.readline().split())
line = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
map_ = [[] for _ in range(n+1)]

# 인덱스를 기준으로 한 map 만들기
for x1, x2 in line:
    map_[x1].append(x2)
    map_[x2].append(x1)

visited = [False] * n
dfs_ = []
def dfs(v):
    visited[v-1] = True
    dfs_.append(str(v))
    for x in sorted(map_[v]):
        if not visited[x-1]:
            dfs(x)

dfs(v)

visited = [False] * n
bfs_ = []
def bfs(v):
    visited[v-1] = True
    queue = deque([v])
    while queue:
        q = queue.popleft()
        bfs_.append(str(q))
        for x in sorted(map_[q]):
            if not visited[x-1]:
                queue.append(x)
                visited[x-1] = True

bfs(v)
print(" ".join(dfs_))
print(" ".join(bfs_))

 

주의사항

- 정점 번호가 작은 것부터 방문하는 것이 탐색 조건이기에 map_에서 원소를 뽑기 전에 이를 오름차순으로 정렬해야한다.

- visited는 리스트 형태이기에 함수를 실행시키면 방문한 곳의 원소는 모두 True로 값이 바뀌게 된다(전역). 따라서 dfs와 bfs를 연달아 시행하기위해선 또 다시 visited를 초기화 시켜줄 필요가 있다.