알고리즘/자료구조 03 - DFS, 스택 DFS, 재귀 DFS

DFS

• 시작 정점에서 한 방향으로 가능한 정점까지 탐색해 나가다가, 더 이상 방문할 정점이 없다면 이전 정점으로 되돌아와서, 방문하지 않은 다른 방향의 정점으로 탐색한다.
• 바로 이전의 정점으로 되돌아가 탐색을 하기 때문에 LIFO의 스택을 이용한다.
• 즉, 스택에는 나중에 돌아올 곳을 기록하게 된다.

 

스택으로 DFS

• list.append(x)는 리스트 끝에 x 1개를 넣는다.

• list.extend(iterable)는 리스트 끝에 iterable의 모든 항목을 넣는다.

# 입력
# 7 8 
# 1 2 
# 1 3 
# 1 4 
# 1 5 
# 2 6 
# 2 7
# 5 6 
# 6 7

NodeNum, EdgeNum = map(int, input().split())
MyMap = [[] for _ in range(NodeNum+1)]

for _ in range(EdgeNum):
    start, stop = map(int, input().split())
    MyMap[start].append(stop)
    MyMap[stop].append(start)

for row in range(1, len(MyMap)):
    print(MyMap[row])
print('=================================')
# [2, 3, 4, 5]
# [1, 6, 7]
# [1]
# [1]
# [1, 6]
# [2, 5, 7]
# [2, 6]

def DFS(start):
    visited = []
    stack = [start]

    while stack:
        here = stack.pop()
        if here not in visited:
            visited.append(here)
            stack.extend(sorted(MyMap[here], reverse=True))
    return visited

print(DFS(1))
# [1, 2, 6, 5, 7, 3, 4]

NodeNum, EdgeNum = map(int, input().split())
MyMap = [[0] * (NodeNum+1) for _ in range(NodeNum+1)]
visited = [0] * (NodeNum+1)
stack = []

for _ in range(EdgeNum):
    row, col = map(int, input().split())
    MyMap[row][col] = 1
    MyMap[col][row] = 1

def findNext(here):
    for next in range(NodeNum+1):
        if MyMap[here][next] and not visited[next]:
            return next

def DFS(here):
    print(here,end=' ')
    visited[here] = True
    while here:
        next = findNext(here)
        if next: # 다음으로 갈 node가 있다면
            stack.append(here) # 돌아올 부모 노드 저장
        while next:
            here = next
            print(here,end=' ')
            visited[here] = True
            next = findNext(here)
            if next:
                stack.append(here)
        if len(stack) != 0:
            here = stack.pop()
        else:
            here = False

DFS(1)
# 방문 순서
# 1 2 6 5 7 3 4

 

재귀로 DFS

import sys
sys.stdin = open("input.txt", 'r')

NodeNum, EdgeNum = map(int, input().split())
MyMap = [[0] * (NodeNum+1) for _ in range(NodeNum+1)]
visited = [0] * (NodeNum+1)

for _ in range(EdgeNum):
    row, col = map(int, input().split())
    MyMap[row][col] = 1
    MyMap[col][row] = 1

for row in range(1, len(MyMap)):
    for col in range(1, len(MyMap[0])):
        print(MyMap[row][col], end='')
    print()
# MyMap
# 0111100
# 1000011
# 1000000
# 1000000
# 1000010
# 0100101
# 0100010

def DFS(here):
    print(here, end=' ')
    visited[here] = True

    for next in range(1, NodeNum+1):
        if MyMap[here][next] and not visited[next]:
            DFS(next)

DFS(1)