#4 탐색 알고리즘 DFS

인접 행렬, 인접 리스트 쓰다가 날아감
ㅋㅋ
ㅋㅋㅋ ㅋㅋ ㅋ ㅋㅋ ....
개웃겨아니안웃겨
책 p134 참고

• DFS (Depth-First Search) : 깊이 우선 탐색
  -> 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
  -> 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘

DFS 는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.
① 탐색 시작 노드를 스택에 삽입하고 ^방문 처리^를 한다.
② 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
③ ②번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

• 방문처리 : 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다.

dfs 예제)

def dfs(graph, v, visited) :
    visited[v] = True
    print(v, end=" ")
    for i in graph[v] :
        if not visited[i] :
            dfs(graph, i, visited)

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
    ]

visited = [False] * 9

dfs(graph, 1, visited)
# 1 2 7 6 8 3 4 5 

처음에 어떻게 6에서 8로 넘어갈 수 있는지 알지 못했다. 잘 생각해보니 7에서 for문이 도는데 이때 graph[7]에 있는 수는 2, 6, 8가 있었다. 2는 이미 True라 패스, 그래서 6이 돌아가는데 6과 인접하고 방문하지 않은 노드가 없으므로 끝. 그 다음에 graph[7] for문이 아직 안끝났기 때문에 8이 들어가는 것이다. 나는 박박대가리 알아서 다행

• 백준 1260
  문제는 DFS와 BFS를 둘 다 구하는 건데 일단 DFS 부분만 풀었다.

import sys

input = sys.stdin.readline

def dfs(graph, val, visit) :
    visit[val] = True
    print(val, end=" ")
    for i in graph[val] :
        if not visit[i] :
            dfs(graph, i, visit)
            
n, m, v = map(int, input().split())

graph = [[] for _ in range(n+1)]

for _ in range(m) :
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()
    
visit = [False] * int(n+1)

dfs(graph, v, visit)