DFS, BFS

왜 DFS와 BFS를 배워야 할까?

🤔 모든 경우의 수를 전부 탐색해야 하는 경우를 위해
ex. 알파고

둘의 차이는 뭘까?

DFS (Depth First Search)

• 끝까지 파고 드는 것
  : 그래프의 최대 깊이 만큼의 공간을 요구
  👍🏻 공간을 적게 씀.
  👎🏻 최단 경로를 탐색하기 쉽지 않음

BFS

• 갈라진 모든 경우의 수를 탐색해보고 오는 것
  👍🏻 최단 경로를 쉽게 찾을 수 있음 - 모든 분기 수를 다 보고 올 수 있기 때문 !
  👎🏻 모든 분기 수를 다 봐야해서 공간 많이 씀, 시간 더 오래걸릴 가능성 있음.

구현 방법

DFS (Breadth First Search)

1. 루트 노드를 스택에 넣는다.
2. 현재 스택의 노드를 빼서 visited에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.
4. 2부터 반복한다.
5. 스택이 비면 탐색을 종료한다.

• 방문 여부?
  + visited 배열을 생성해서 기록!
  

BFS (Depth First Search)

• 현재 인접한 노드를 먼저 방문해야함

1. 루트 노드를 큐에 넣는다.
2. 현재 큐의 노드를 빼서 visited에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
4. 2부터 반복한다.
5. 큐가 비면 탐색을 종료한다.

💻 풀다보니 나온 주요 코드들

def bfs(x, y):
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, -1), (-1, 1)]

    que = deque()
    que.append((x, y))

    island[x][y] = 0

    while que:
        n = que.popleft()

        for i in range(8):
            nx = n[0] + directions[i][0]
            ny = n[1] + directions[i][1]

            if (0<=nx<h) and (0<=ny<w):
                if int(island[nx][ny]) == 1:
                    island[nx][ny] = 0
                    que.append((nx, ny))

def dfs(x, y):
    # 현재 색상(좌표) 방문
    visited[x][y] = True
    cur_color = matrix[x][y]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0<=nx<N) and (0<=ny<N):
            # 현재 좌표의 색상과 상하좌우 좌표에 있는 색상이 같으면 dfs로 추가
            if visited[nx][ny] == False:
                if matrix[nx][ny] == cur_color:
                    dfs(nx, ny)