DFS
DFS란?
DFS는 깊이 우선 순회로, 갈 수 있는 한 최대 깊이로 간 후, 없을 때 한 칸 다시 위로 올라와서 다시 깊이가고 이런 동작을 반복하게 됩니다.
ex) 1번 노드부터 시작해서 쭉 내려간다 -> 3 -> 7 -> 8 -> 끝이네? -> 7로 올라감 -> 인접 노드 없네? -> 3으로 올라감 -> 인접노드 5 있네! -> 쭉 탐색 -> 또 없으면 올라가고 올라가고 해서 시작노드까지 온 후 갈 곳이 없을 때 종료
수도코드
- 내가 지금 있는 노드가 방문됐다고 체크
- 인접한 노드 반복 돌리기
- 방문되지 않은 노드가 있다면? -> 그 노드에 대해서 재귀
수도코드를 이용하여 코드짜기
-
문제
그냥 DFS를 수행한 결과를 출력하면 된다.
-
입력
정점의 개수, 간선의 개수, 탐색을 시작할 정점의 노드가 주어진다.
-> 그림으로 나타내면 이렇다
정점 4개에 간선 5개 / 탐색을 시작할 노드는 1
-
출력
-> DFS의 탐색 결과를 나타낸다.
-
코드 짜기
- 입력 받아서 인접행렬로 만들기from collections import deque N, line, s = list(map(int, input().split())) arr = [[0 for _ in range(N+1)] for _ in range(N+1)] for i in range(line): x, y = map(int, input().split()) arr[x][y] = 1 arr[y][x] = 1-> 입력으로는 1부터 값이 들어오는데, 실제 코드의 인덱스는 0부터 시작하므로 N이 아니라 최대 배열을 N+1로 설정한다.
- dfs 수도코드로 짠 dfs 함수
# 1. 내가 지금 있는 노드가 방문됐다고 체크 visited1[start] = 1 # 2. 인접한 노드 반복 돌리기 for i in range(1, N+1): # 3. 방문되지 않은 노드가 있다면? -> 그 노드에 대해서 재귀 if visited1[i]==0 and arr[start][i]==1: dfs(i)
-
여기에 정점 노드들을 출력하는 코드만 추가하면 된다
# 1. 내가 지금 있는 노드가 방문됐다고 체크 visited1[start] = 1 # 1-1. 정점 노드들 출력 print(start, end=' ') # 2. 인접한 노드 반복 돌리기 for i in range(1, N+1): # 3. 방문되지 않은 노드가 있다면? -> 그 노드에 대해서 재귀 if visited1[i]==0 and arr[start][i]==1: dfs(i)
총 코드
from collections import deque
N, line, s = list(map(int, input().split()))
arr = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(line):
x, y = map(int, input().split())
arr[x][y] = 1
arr[y][x] = 1
visited1 = [0 for i in range(N+1)]# dfs의 방문기록
def dfs(start):
visited1[start] = 1
print(start, end=" ")
for i in range(1, N+1):
if visited1[i]==0 and arr[start][i]==1:
dfs(i)
dfs(s)번외(bfs 추가)
from collections import deque
N, line, s = list(map(int, input().split()))
arr = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(line):
x, y = map(int, input().split())
arr[x][y] = 1
arr[y][x] = 1
def bfs(start):
deq = deque()
visited = [0 for i in range(N+1)]
visited[start] = 1
deq.append(start)
while len(deq)!=0:
current = deq.popleft()
print(current, end=' ')
for i in range(1, N+1):
if(arr[current][i]==1 and visited[i]==0):
visited[i] = 1
deq.append(i)
visited1 = [0 for i in range(N+1)]# dfs의 방문기록
def dfs(start):
visited1[start] = 1
print(start, end=" ")
for i in range(1, N+1):
if visited1[i]==0 and arr[start][i]==1:
dfs(i)
dfs(s)
print()
bfs(s)
Hello Velog