DFS with python

🔎 DFS란?

• Depth First Search의 약자로, 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조입니다.
  🪄 그래프 자료에서 데이터를 탐색하는 알고리즘이라고도 부릅니다.

• 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.
• 또, 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.
• 위 과정을 반복한다.

🔎 DFS의 기본 원칙

• DFS에서 데이터를 찾을 때는 항상 앞으로 찾아 가야할 노드와 이미 방문한 노드를 기준으로 데이터를 탐색합니다.
  따라서, 특정 노드가 앞으로 찾아 가야할 노드라면 계속 검색을 하는것이고 이미 방문한 노드면 무시하거나 저장하면 됩니다.

주어진 그래프

graph = {
     1: [2, 3, 4],
     2 : [5],
     3: [5],
     4: [],
     5:  [6,7],
     6: [],
     7: [3],
 }

재귀적 DFS구현

def dfs_recursive(node,visited):
    # 방문처리
    visited.append(node)
	
    # 인접 노드 방문
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj,visited)

        return visited

• dfs_recursive 함수는 재귀적으로 DFS를 수행합니다.
  node : 현재 방문하고 있는 노드입니다
  visited : 방문한 노드를 기록하는 리스트입니다.

1. 먼저 visited 리스트에 현재 노드를 추가하여 방문을 처리합니다.
2. graph[node] 는 현재 노드의 인접 노드들을 나타내는 리스트입니다.
3. 각 인접 노드에 대해 방문하지 않은 경우에만 재귀적으로 dfs_recursive 함수를 호출하여 그 노드를 방문합니다.
4. 모든 인접 노드를 방문한 후 visited 리스트를 반환합니다.

스택을 이용한 DFS 구현

def dfs_stack(start):
    visited = [] # 방문한 노드를 기록하는 리스트
    stack = [start] # 방문할 노드를 담는 스택, 시작 노드로 초기화

    # 스택에 방문할 노드가 남아있는 한 아래 로직을 반복한다.
    while stack:
        top = stack.pop()  # 제일 최근에 삽입된 노드를 꺼냄
        visited.append(top) # 방문 처리 
    
        for adj in graph[top]:   # 현재 노드의 인접 노드들을 탐색
            if adj not in visited: # 인접 노드가 방문되지 않았다면
                stack.append(adj) # 스택에 추가하여 나중에 방문

        return visited # 방문한 순서대로 노드들을 반환

visited 리스트 : 방문한 노드를 기록하기 위한 리스트입니다.
stack 리스트 : DFS를 위한 스택입니다. 초기에는 시작 노드인 'start'로 설정(초기화)됩니다.
while stack : 스택이 비어질 때까지 반복합니다. 스택에 남아있는 노드들은 방문할 노드들을 의미합니다.
top = stack.pop() : 스택에서 맨 위(최근에 추가된) 노드를 꺼내어 'top'에 할당합니다. 이 노드를 방문 처리합니다.
visitde.append(top): 방문한 노드를 visited 리스트에 추가(append)합니다
for adj in graph[top] : 현재 꺼낸 노드 top의 인접 노드들을 탐색합니다.
if adj not in visited : 인접 노드가 방문되지 않았다면, 스택에 추가하여 나중에 방문합니다.
return visited : 모든 노드들을 방문한 후, 방문한 순서대로 노드들을 담은 visited 리스트를 반환합니다.

🔦 섬의 개수 찾기

체감 난이도 : ⭐️⭐️⭐️⭐️☆

def island_dfs_stack(grid):
    # 상, 하, 좌, 우 방향을 나타내는 배열
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]

    # 그리드의 행과 열 길이
    rows, cols = len(grid), len(grid[0])

    # 섬의 개수를 세는 변수 'cnt'
    cnt = 0

    # 그리드의 각 셀을 하나씩 탐색
    for row in range(rows):
        for col in range(cols):
            # 현재 셀이 육지('1')가 아니면 건너뜀
            if grid[row][col] != '1':
                continue

            # 새로운 섬을 발견했으므로 섬 개수를 증가시킴
            cnt += 1

            # 스택을 초기화하고 현재 셀을 스택에 추가
            stack = [(row,col)]

            # 스택이 비어있을 때까지 반복
            while stack:
                x,y = stack.pop() # 스택에서 하나의 셀을 꺼냄
                grid[x][y] = '0' # 꺼낸 셀을 '0'으로 표시하여 방문한 것으로 처리

                # 네 방향을 탐색
                for i in range(4):
                    nx = x + dx [i] # 새로운 x 좌표
                    ny = y + dy [i] # 새로운 y 좌표

                    # 새로운 좌표가 그리드 범위를 벗어나거나 , 육지가 아니면 건너뜀
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != '1':
                        continue

                    # 스택에 새로운 좌표를 추가하여 DFS 진행
                    stack.append((nx,ny))

                # 한번의 DFS 탐색이 끝나면 해당 섬의 탐색을 완료하고 다음 셀로 이동

            return cnt # 섬의 개수를 반환

🤕