비선형구조인 그래프 구조는 그래프로 표현된 자료를 빠짐 없이 검색하는 것이 중요하다.
- DFS (깊이 우선 탐색)
- BFS (너비 우선 탐색)
1. DFS란?
시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 갈선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 반복하는 순회방법
→ 가장 마지막에 만났던 갈림길의 정점으로 돌아가기 위해서 “스택” 을 사용한다.
2. DFS의 기본 구조
(출처: 관광이 블로그)
DFS를 구하기 위한 준비물은 다음과 같다…
- 현재 노드와 인접한 노드의 정보를 담은 인접리스트 혹은 인접 행렬
- 방문했는지 여부를 체크할 수 있는 리스트
- 마지막 방문 위치를 담을 수 있는 스택
2-1. 인접리스트 혹은 인접 행렬 구하기
리스트로 입력받기
(cf. 방향도 중요한데, 일방향인지 양방향 통행 가능인지에 따라 받는 방법도 달라진다. 이 경우에는 양방향으로 가정하고 리스트를 받았다.)
# V는 노드의 개수, E는 간선의 개수
# 입력 형식은
# 8 10 # V E
# 1 2 # 이하로는 간선이 연결된 노드 넘버
# 1 3
# 2 4
# 2 5
# 3 6
# 3 7
# 4 8
# 5 8
# 6 8
# 7 8입력
V, E = map(int, input().split())
adj = [[] for _ in range(V+1)]
for _ in range(E):
a, b = map(int, input().split()) #a는 adj안에 있는 리스트의 인덱스, b는 노드 번호이다.
adj[a].append(b)
adj[b].append(a) # 만약 일방통행이라면 이 코드를 삭제하면 된다.
print(adj)
출력
adj = [
[],
[2,3],
[1,4,5],
[1,6,7],
[2,8],
[2,8],
[3,8],
[3,8],
[4,5,6,7]
]이 방법은 인접한 노드의 위치를 바로 알 수 있다는 장점이 있지만,
append를 사용하기 때문에 시간이 오래걸리고. 위의 예시처럼 예쁘게 오름차순으로 주어지지 않은 경우,
순서가 뒤죽박죽으로 append 될 수 있다는 단점도 있다.
행렬로 입력받기
입력
V, E = map(int, input().split())
adj = [[0]*(V+1) for _ in range(V+1)]
for _ in range(E):
a, b = map(int, input().split())
adj[a][b] = 1
adj[b][a] = 1 # 일방향 통행일 경우 이 부분을 삭제하면 된다.
print(adj)출력
[
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 1, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 1, 1, 1, 1, 0]
]
이 방법은 입력받는 순서에 상관없이 인접하면 1, 인접하지 않으면 0으로 표현한다.
양방향 통행이 가능한 경우, 좌상단→우하단으로 가는 대각선을 기준으로 대칭이라는 특징도 가지고 있다.
또한 이미 [0] 으로 채워진 리스트에 다른 값만 입력해주는 것이기 때문에, 숫자가 커지면 단순 append 보다 처리속도가 빠르다.
2-2. 반복문(while)을 이용해서 DFS 작성하기
위에서 준비물 1을 완성했기 때문에, 준비물 2와 3은 함수 안에서 정의하고 사용하면 된다.
전체적인 흐름은 다음과 같다.
def dfs(s,V):
# 현재 위치는 s, 노드의 개수는 V개
# 방문했는지 여부를 기록할 리스트를 만든다.
# 마지막으로 방문한 위치를 기록할 stack을 만든다.
# 초기 위치를 방문했다고 기록한다.
# 돌아갈 곳이 없을 때까지 반복한다.
# 현재 위치에 인접한 리스트를 돌면서
# 인접하면서 아직 방문하지 않은 곳이 있다면.
# 현재 위치를 stack에 넣는다.
# 인접한 곳으로 이동한다.
# 이동한 후에, 현재 위치를 출력하고, 방문했다고 표시한다.
# break를 통해 for문을 빠져나온다.
# for문을 다 돌고, 더이상 갈 곳이 없다면
# stack이 비어있지 않다면,
# 현재 위치를 stack의 맨 마지막 곳으로 이동시킨다.
# stack이 비어서 더이상 갈 곳이 없다면.
# while문을 탈출해서 나온다.adj = [
[],
[2,3],
[1,4,5],
[1,6,7],
[2,8],
[2,8],
[3,8],
[3,8],
[4,5,6,7]
]def dfs1(s,V):
# 현재 위치는 s, 노드의 개수는 V개
# 방문했는지 여부를 기록할 리스트를 만든다.
visited = [0]*(V+1) # 인덱스의 편의를 위해서 V+1개를 만든다.
# 0번 인덱스는 사용하지 않는다.
# 방문하지 않으면 0, 방문하면 1로 표시하려고 한다.
# 마지막으로 방문한 위치를 기록할 stack을 만든다.
stack = []
# 초기 위치를 방문했다고 기록한다.
visited[s] = 1
print(s)
# 돌아갈 곳이 없을 때까지 반복한다.
while True:
# 현재 위치에 인접한 리스트를 돌면서
for i in adj[s]:
# 인접하면서 아직 방문하지 않은 곳이 있다면.
if visited[i] == 0:
# 현재 위치를 stack에 넣는다.
stack.append(s)
# 인접한 곳으로 이동한다.
s = i
visited[s] = 1
print(s) # 이동했으면 출력한다.
# 이동한 후에는 break를 통해 for문을 빠져나온다.
break
# 이제 바뀐 s에대해서 다시 반복문이 돌아간다.
# for문을 다 돌고, 더이상 갈 곳이 없다면
else:
# stack이 비어있지 않다면,
if stack: # 이 표현은 stack 안에 원소가 있으면 True가 나와서 실행된다.
# 현재 위치를 stack의 맨 마지막 곳으로 이동시킨다.
s = stack[-1]
# stack이 비어서 더이상 갈 곳이 없다면.
else:
# while문을 탈출해서 나온다.
break
dfs1(1,8) # 1 2 4 8 5 6 3 7[
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 1, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 1, 1, 1, 1, 0]
]
def dfs2(s,V):
# 현재 위치는 s, 노드의 개수는 V개
# 방문했는지 여부를 기록할 리스트를 만든다.
visited = [0] * (V+1)
# 마지막으로 방문한 위치를 기록할 stack을 만든다.
stack = []
# 초기 위치를 방문했다고 기록한다.
visited[s] = 1
print(s)
# 돌아갈 곳이 없을 때까지 반복한다.
while True:
# 현재 위치에 인접한 리스트를 돌면서
for i in range(V+1):
# 인접하면서 아직 방문하지 않은 곳이 있다면.
if adj[s][i] == 1 and visited[i] == 0:
# 현재 위치를 stack에 넣는다.
stack.append(s)
# 인접한 곳으로 이동한다.
s = i
visited[i] = 1
print(s)
# 이동한 후에는 break를 통해 반복문을 빠져나온다.
break
# for문을 다 돌고, 더이상 갈 곳이 없다면
else:
# stack이 비어있지 않다면,
if stack:
# 현재 위치를 stack의 맨 마지막 곳으로 이동시킨다.
s = stack.pop()
# stack이 비어서 더이상 갈 곳이 없다면.
else:
# while문을 탈출해서 나온다.
break
dfs2(1,8) # 1 2 4 8 5 6 3 72-3. 재귀함수를 이용해서 DFS 작성하기
adj = [
[],
[2,3],
[1,4,5],
[1,6,7],
[2,8],
[2,8],
[3,8],
[3,8],
[4,5,6,7]
]
def dfs3(s):
# 재귀함수를 사용하면, 맨 처음 위치를 입력받는다.
print(s)
visited[s] = 1
for i in adj[s]:
if visited[i] == 0:
dfs(i)
V, E = map(int, input().split())
adj = [[] for _ in range(V+1)]
for _ in range(E):
a, b = map(int, input().split()) #a는 adj안에 있는 리스트의 인덱스, b는 노드 번호이다.
adj[a].append(b)
adj[b].append(a) # 만약 일방통행이라면 이 코드를 삭제하면 된다.
visited = [0]*(V+1)
dfs3(1) # 1 2 4 8 5 6 3 7[
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 1, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 1, 1, 1, 1, 0]
]
def dfs4(s):
print(s)
visited[s] = 1
for i in range(V+1):
if adj[s][i] ==1 and visited[i] == 0:
dfs4(i)
V, E = map(int, input().split())
adj = [[0]*(V+1) for _ in range(V+1)]
for _ in range(E):
a, b = map(int, input().split())
adj[a][b] = 1
adj[b][a] = 1
visited = [0]*(V+1)
dfs4(1)Uploaded by N2T