문제
그래프를 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문제 분석
간단하게 DFS, BFS를 파이썬으로 실행 할 수 있는지 요구 하는 문제다.
DFS, BFS를 하려면 먼저 그래프에 대한 이해를 해야한다.
그래프
그래프는 G라고 표시한다.
그리고 G는 G(V,E)라고 표시하며 각 요소는 아래와 간다.
- V(vertex) : 정점의 집합
특성을 가지는 객체를 의미하며 노드 라고도 한다. - E(edge): 간선의 집합
정점들 간의 관계를 의미하며 link 라고도 한다.
그래프 종류
무향 그래프
양방향의 의미. 즉, (A,B) = (B,A) 순서가 상관 없다. !
방향 그래프
한쪽 방향으로만 갈 수 있는 특징. <A,B> ≠ <B,A> 이다.
그래프 특성(무향 그래프)
차수
차수는 하나의 정점 입장에서 다른 정점이 얼마나 연결 되어 있는지를 나타낸다.
위 그림에서 4입장에서는 3하나만 연결 되어 있으니 이때의 차수는 1이라고 한다.
그럼 3입장에서는 1, 4, 5 이렇게 3개가 연결되어 있으니 차수는 3 이다.
💡 모든 차수의 합 = 에지 개수의 2배
방향 그래프
이 그래프는 방향이 있기 때문에 차수를
- 진입 : 외부에서 오는 에지 수
- 진출 : 외부로 나가는 에지 수
로 구분한다.
예를 들어 그림(a)를 보면 정점 B입장에서
- 진입 차수 : 1개(A)
- 진출 차수 : 2개(C,E)
로 나타낼 수 있음.
💡 진입 차수의 합 == 진출 차수의 합 == 그래프 내 모든 에지의 수
그래프의 표현 방법
인접 행렬
파이썬에서 그래프를 표현하는 방법 중 하나는 인접 행렬을 사용하는 것이다. 인접 행렬은 그래프의 정점들간의 연결관계를 행렬로 표현한 것이다. 보면 알겠지만 행렬의 각 칸은 그래프의 한 정점에서 다른 정점으로 가는 경로가 존재하는지 안하는지를 나타낸다.
점 (정점)의 개수를 k 라고 했을 때 k x k의 행렬을 만들자.
각 행은 해당 점의 연결 상태를 의미한다.
이때의 공간 복잡도는 O(n^2)으로 매우 비효율적이다.
예시
3개의 정점 A,B,C가 있다고 치자. 그런 후 아래 처럼 연결되어 있다고 해보자
A - B
|
C위 그래프의 인접 행렬은 아래와 같다.
A B C
A 0 1 1
B 1 0 0
C 1 0 01은 경로가 존재함(가능) 0은 존재 안함(불가능)을 나타낸다.
행은 출발을, 열은 도착을 나타낸다.
(A,B) = A에서 B로 가는 경로의 존재를 나타낸다.
만드는 방법
#정점의 개수
n = 3
# 인접 행렬을 0으로 초기화하기
adj_matrix = [[0]*n for _ in range(n)]
# A, B, C 정점은 인덱스 0, 1, 2로 표현
# A와 B가 연결되어 있음
adj_matrix[0][1] = 1
adj_matrix[1][0] = 1
# B와 C가 연결되어 있음.
adj_matrix[0][2] = 1
adj_matrix[2][0] = 1
# 인접 행렬 출력
for row in adj_matrix:
print(' '.join(map(str, row)))이렇게 하면 된다.
이렇게 하면 두 정점 간의 연결 여부를 O(1)의 시간 복잡도로 빠르게 확인할 수 있는 장점이 있지만 정점의 수가 많을 때는 많은 메모리를 소비한다.
혹은 인접 리스트로 표현하는 방법이 있는데 파이썬은 포인터가 없어서 출발을 키로 도착을 값으로 해서 표현하기도 한다.
DFS와 BFS
DFS
깊이 우선 탐색이라고 한다.
- 그래프에서 깊이가 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 or 재귀를 이용한다.
동작은 아래와 같이 된다.
- 현재 노드를 방문처리한다.
- 현재 노드와 연결된 모든 노드 중 방문하지 않은 노드를 방문함.
- 모든 노드를 방문할때 까지 반복.
- 그래프, 트리에서 모든 노드를 탐색하는데 사용함.
- 순환 알고리즘(자기 자신을 호출)이므로 노드 방문 여부 리스트가 필요함.
BFS
너비 우선 탐색이라고 한다.
- 큐를 이용한다.
동작은 아래처럼 이뤄진다.
- 현재 노드를 큐에 삽입하고 방문처리 함.
- 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
- 이 짓을 모든 노드를 방문할때 까지 반복한다.
- 그래프 혹은 트리에서 모든 노드를 탐색하는데 사용함.
- 재귀 함수이므로 노드 방문 여부 리스트가 필요함.
문제 코드
from collections import deque
N, M, V = map(int, input().split())
graph = [[] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split())
graph[a][b] = True
graph[b][a] = True
visited1 = [False] * (N + 1) # dfs의 방문기록
visited2 = [False] * (N + 1) # bfs의 방문기록
def bfs(V):
q = deque([V]) # pop메서드의 시간복잡도가 낮은 덱 내장 메서드를 이용한다
visited2[V] = True # 해당 V 값을 방문처리
while q: # q가 빌때까지 돈다.
V = q.popleft() # 큐에 있는 첫번째 값 꺼낸다.
print(V, end=" ") # 해당 값 출력
for i in range(1, N + 1): # 1부터 N까지 돈다
if not visited2[i] and graph[V][i]: # 만약 해당 i값을 방문하지 않았고 V와 연결이 되어 있다면
q.append(i) # 그 i 값을 추가
visited2[i] = True # i 값을 방문처리
def dfs(V):
visited1[V] = True # 해당 V값 방문처리
print(V, end=" ")
for i in range(1, N + 1):
if not visited1[i] and graph[V][i]: # 만약 i값을 방문하지 않았고 V와 연결이 되어 있다면
dfs(i) # 해당 i 값으로 dfs를 돈다.(더 깊이 탐색)
dfs(V)
print()
bfs(V)