DFS

트리의 순회와 같이 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색(search) 알고리즘이라고 한다.
그래프는 트리보다 구조가 훨씬 복잡할 수 있기 때문에 탐색 과정에서 얻어지는 정보가 아주 중요하다. 탐색 과정에서 어떤 간선이 사용되었는지, 또 어떤 순서로 정점들이 방문되었는지를 통해 그래프의 구조를 알 수 있다.
탐색 알고리즘 중 가장 널리 사용되는 두 가지가 DFS, BFS이다.

DFS는 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다.
현재 정점과 인접한 간선들을 하나씩 검사하다가 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 것으로 더 이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아감

1. 재귀 호출

def dfs(node):
  Visited[node] = True
  print(node, end = ' ')

  for next in range(N):
    if not Visited[next] and Graph[node][next]:
      dfs(next)

if __name__ == "__main__":
  N, E = map(int, input().split())
  Visited = [False for _ in range(N)]
  Graph = [[0 for _ in range(N)] for _ in range(N)]

  values = list(map(int, input().split()))
  for i in range(E):
    u, v = values[i * 2], values[i * 2 + 1]
    Graph[u][v] = Graph[v][u] = 1

  dfs(0)

입력
5 6
0 1 0 2 1 3 1 4 2 4 3 4

출력
0 1 3 4 2

2. 스택(Stack)

def dfs(node):
  Visited = [False for _ in range(N)]
  stack = []
  stack.append(node)
  while stack:
    curr = stack.pop()
    if Visited[curr]: continue

    Visited[curr] = True
    print(curr, end =  ' ')
    for next in range(N):
      if not Visited[next] and Graph[curr][next]:
        stack.append(next)

if __name__ == "__main__":
  N, E = map(int, input().split())
  Graph = [[0 for _ in range(N)] for _ in range(N)]

  values = list(map(int, input().split()))
  for i in range(E):
    u, v = values[i * 2], values[i * 2 + 1]
    Graph[u][v] = Graph[v][u] = 1

  dfs(0)

입력
5 6
0 1 0 2 1 3 1 4 2 4 3 4

출력
0 2 4 3 1

DFS 활용 - Flood fill

입력으로 들어오는 1은 벽으로 생각한다. 현재 위치에서 상,하,좌,우로 움직이면서 벽에 가로막히지 않는 선에서 0을 color로 색칠할 수 있는 경우를 표현하는 문제

def dfs(r, c, color):
  visited = [[False for _ in range(N)] for _ in range(N)]
  stack = []
  stack.append((r,c))

  while stack:
    curr = stack.pop()
    if visited[curr[0]][curr[1]]: continue

    visited[curr[0]][curr[1]] = True
    Board[curr[0]][curr[1]] = color  

    for i in range(4):
      nr = curr[0] + D[i][0]  #이 부분 제대로 이해하기
      nc = curr[1] + D[i][1]
      if nr < 0 or nr > N-1 or nc < 0 or nc > N - 1: continue
      if visited[nr][nc]: continue
      if Board[nr][nc] == 1: continue
      stack.append((nr, nc))




if __name__ == "__main__":
  D = ((-1,0), (1,0), (0,-1), (0,1)) #움직일 수 있는 방향 표시(동, 서, 남, 북)
  N = int(input())
  Board = [list(map(int, input().split())) for _ in range(N)]

  sr, sc, color = map(int, input().split()) #start row, start column, color
  dfs(sr, sc, color)

  for i in range(N):
    for j in range(N):
      print(Board[i][j], end = " ")
    print()

입력
5
0 0 0 0 0
0 0 0 1 1
0 0 0 1 0
1 1 1 1 0
0 0 0 0 0
1 1 3

출력
3 3 3 3 3
3 3 3 1 1
3 3 3 1 0
1 1 1 1 0
0 0 0 0 0