🚶‍♂️Road to 코테(9) - DFS

본 게시물은 BaaarkingDog님의 실전 알고리즘 강의를 통해 공부한 것을 정리합니다.

[추가] 용감하게 시작하는 코딩테스트

[추가] 코딩 테스트 합격자 되기 - 파이썬

[추가] 좌충우돌, 파이썬으로 자료구조 구현하기

DFS

다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘

과정

1. 시작하는 칸을 스택에 넣고 방문했다는 표시 남김
2. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해
3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입
4. 스택이 빌 때 까지 2번을 반복
   모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N).
   ※ 큐를 쓰면 BFS이고 스택을 쓰면 DFS이다.

BFS에서는 popleft를 했다면 DFS에서는 pop을 한다. 즉 나중에 들어온 것을 먼저 탐색한다.

BFS에서 시작점을 중앙으로 잡았다면 상하좌우로 탐색하는 것을 알 수 있다.
DFS에서는 시작점을 중앙으로 잡았다면 하나의 분기점을 모두 탐색해야 다음 방향으로 나갈 수 있다.
하지만, 현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져 있다는 성질이 DFS에서는 성립 되지 않는다.
즉, 거리 계산시 DFS를 사용할 수 없다. 결국, 다차원 배열에서 BFS 대신 DFS를 써야하는 일이 없다.
-> DFS는 트리와 그래프에서 필요하므로 알고 있어야 한다.

기본 구조

import sys

N, M = map(int, sys.stdin.readline().split())
mat = [
  [0, 1, 1, 1, 1, 1],
  [0, 1, 0, 0, 0, 1],
  [0, 1, 0, 1, 0, 1],
  [0, 1, 0, 1, 0, 0],
  [0, 0, 0, 1, 1, 0],
  [1, 1, 1, 1, 1, 0]
  ]
# for _ in range(N):
#     row = list(map(int, input().split()))
#     mat.append(row)
print(mat)


visited=[[False]*M for _ in range(N)]

def DFS(visited,y,x):
  dx=[-1,0,0,1]
  dy=[0,1,-1,0]
  visited[y][x]=True
  stack=[]
  stack.append([y,x])
    
  
  while stack:
    value=stack.pop()
    for i in range(4):
      nx=value[1]+dx[i]
      ny=value[0]+dy[i]
      if (ny<0 or nx<0  or ny>=M or nx>=N):
        continue
      if mat[ny][nx]==1:
        continue
      if not visited[ny][nx]:
        stack.append([ny,nx])
        visited[ny][nx]=True
      
DFS(visited,0,0)