📌문제
그래프를 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💡Idea
DFS와 BFS 알고리즘을 그대로 사용해서 구현한 뒤에 출력을 하면 되는 문제이므로, 큐를 사용하여 BFS를, 재귀 함수를 사용하여 DFS를 구현해보았습니다.
DFS와 BFS의 구현과 개념에 대해서 자세히 알아보고 싶다면 여기를 눌러주세요!
💻코드
from collections import deque
import sys
def dfs(edge, visited, n, v):
print(v, end=' ') # 현재 탐색하는 노드 출력
for i in range(1, n+1): # 연결되어 있는 노드 확인 위한 인접 행렬 확인
if edge[v][i] == 1 and i not in visited:
visited.append(i)
dfs(edge, visited, n, i)
def bfs(edge, n, v):
# 큐와 방문 여부 확인 리스트에 첫번째 노드 삽입
deq = deque([v])
visited = [v]
while deq: # 큐에 아무 노드가 없을 때까지 반복
current = deq.popleft()
print(current, end=' ')
for i in range(1, n+1): # 인접 행렬 확인
if edge[current][i] == 1 and i not in visited:
deq.append(i)
visited.append(i)
input = sys.stdin.readline
n, m, v = map(int, input().split())
edge = [[0 for x in range(n+1)] for x in range(n+1)]
for i in range(m): # 인접 행렬으로 그래프 표현
n1, n2 = map(int, input().split())
edge[n1][n2] = edge[n2][n1] = 1
dfs(edge, [v], n, v)
print()
bfs(edge, n, v)
📝코드 설명
변수
edge: 그래프를 표현한 이차원 리스트로, 각 노드들이 연결되어 있으면 1의 값을, 그렇지 않으면 0의 값을 가짐.n: 노드의 수m: 노드를 연결하는 간선의 수v: 시작 노드visited: 노드의 재탐색을 방지하기 위한 방문 여부 기록 리스트deq:bfs의 구현에서 큐를 구현하기 위하여 사용한deque
그래프 생성
인접 행렬을 사용하여 그래프를 만들어보았습니다.
그래프 이론에서, 인접 행렬(adjacency matrix)은 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각 행렬이다.
DFS
DFS는 재귀적인 방법으로 구현해보았습니다.
주어진 노드와 연결되어 있는 노드들 중, 아직 탐색되지 않았던 노드라면 해당 노드와 연결되어 있는 또 다른 노드들을 탐색하기 위해 dfs 함수를 실행합니다.
BFS
BFS는 큐를 이용하여 구현해보았습니다.
큐는 collections의 deque를 사용하였습니다. 큐에서 노드를 하나씩 꺼낸 뒤, 연결되어 있는 노드들 중 아직 탐색하지 않았던 노드들을 큐에 다시 넣어주는 식으로 구현하였습니다.
그리고 이를 큐에 노드가 하나도 없을 때까지 반복하였습니다.
