그래프 - DFS, BFS

그래프

자료구조는 크게 비선형 구조와 선형 구조로 나뉘게 된다. 

선형 구조는 앞에서 배운 연결 리스트, 스택, 큐, 힙과 같이 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있다면, 비선형 구조는 표현에 초점이 맞춰져 있다.

 

여기서 그래프는 연결 관계에 초점이 맞춰져 있는 자료구조이다.

 

그래프에서 사용되는 용어는 다음과 같다.

• 노드(Node): 연결 관계를 가진 각 데이터
• 간선(Edge): 노드 간의 관계를 표시한 선
• 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

그래프를 컴퓨터에서 표현하는 방법에는 두 가지가 있다.

1. 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현
2. 인접 리스트(Adjacency List): 연결 리스트로 그래프의 연결 관계를 표현

             2 - 3
             ⎜       
       0 - 1                     => 이를 인접 행렬, 2차원 배열로 나타내면 다음과 같다. 

 

각 원소는 두 노드가 인접해있는지 여부를 True, False로 정보를 가지고 있다.

이번에는 인접 리스트로 표현해보자.

각 원소는 본인과 인접해 있는 노드 정보를 가지고 있다.

우리는 주로 인접리스트를 사용할 것이지만, 간선에 가중치가 있는 경우 인접리스트 표현이 복잡해지기 때문에 인접 행렬로 바꿀 수 있어야 한다.

DFS

DFS는 Depth First Search의 약자로, 갈 수 있는만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조이다.

즉, 인접한 노드 중 방문하지 않은 노드들을 저장해두고, 가장 마지막에 넣은 노드를 꺼내서 탐색했다. => 스택 사용

(이때, visited라는 배열에 방문한 노드를 기록해둔다.)

• 시작 노드를 정하고 여기에서 시작한다.
• 현재 방문한 노드를 visited에 추가한다.
• 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다.
• 2부터 반복한다.

구현을 재귀와 스택으로 할 수 있는데, 스택을 주로 이용하자.

def dfs_recursive(graph, node, visited):
    # 방문처리
    visited.append(node)

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

    return visited


def dfs_stack(graph, 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

BFS

BFS는 DFS와 다르게 현재 인접한 노드 먼저 방문해야한다.

BFS는 인접한 노드 중 방문하지 않은 노드들을 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다.

=> 큐 이용!

from collections import deque

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

def bfs_queue(graph, start):
    visited = [start]
    q = deque([start])

    while q:
        node = q.popleft()
        for adj in graph[node]:
            if adj not in visited:
                q.append(adj)
                visited.append(adj)

    return visited
    
assert bfs_queue(graph, 1) == [1, 2, 5, 9, 3, 6, 8, 10, 4, 7]

문제 - 섬의 개수 

문제

 '1'(육지)과 '0'(물)으로 구성된 지도를 나타내는 m x n 크기의 이진 격자가 주어질 때, 섬의 개수를 반환합니다.

섬은 물로 둘러싸여 있으며 인접한 땅을 가로 또는 세로로 연결하여 형성됩니다.

예시

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

설명

DFS와 BFS 를 활용해서 시작점으로부터 상하좌우로 그리드를 돌아다니고, 특정 위치를 돌면 그리드에서 해당 노드를 돌았다고 0으로 수정한다. 특정 섬을 다 돌았으면 다시 stack 또는 queue에 남아있는 위치를 기준으로 다시 시작한다. 
(해당 문제에서는 방문한 노드들은 visited 배열에 따로 저장하지 않고, '1'을 '0'으로 마킹해주는 방식으로 진행했다.)

<상하좌우 이동 방법>
dx = [0, 0, 1, -1]   
dy = [1, -1, 0, 0]
for i in range(4):                 
            nx = x + dx[i]           
            ny = y + dy[i]

구현

def island_dfs_stack(grid):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    rows, cols = len(grid), len(grid[0])
    cnt = 0

    for row in range(rows):
        for col in range(cols):
            if grid[row][col] != '1':
                continue

            cnt += 1
            stack = [(row, col)]

            while stack:
                x, y = stack.pop()
                grid[x][y] = '0'
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != '1':
                        continue
                    stack.append((nx, ny))
                    
def island_bfs_stack(grid):
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    rows = len(grid)
    cols = len(grid[0])
    cnt = 0

    for row in range(rows):
        for col in range(cols):
            if grid[row][col]!='1':
                continue

            cnt += 1
            queue = deque()
            queue.append((row,col))

            while queue:
                x,y = queue.popleft()
                grid[x][y] = '0'
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if nx < 0 or nx >= rows or ny <0 or ny >= cols or grid[nx][ny] != '1':
                        continue
                    queue.append((nx,ny))
    
    return cnt


assert island_dfs_stack(grid=[
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]) == 1
assert island_dfs_stack(grid=[
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]) == 3

문제 - 미로 탈출 경로 찾기

문제

• N x M 크기의 미로가 주어집니다. 미로는 0과 1로 구성되어 있으며, 0은 이동할 수 없는 벽을 나타내고, 1은 이동할 수 있는 경로를 나타냅니다.
• 시작 위치는 (0, 0)이며, 미로의 출구는 (N-1, M-1)에 위치해 있습니다.
• 최단 경로로 미로를 탈출하는 방법을 찾는 프로그램을 작성하세요. 이동은 상하좌우로만 가능합니다.
• BFS 알고리즘을 사용하여 미로의 모든 경로를 탐색합니다.
•  
•  
•  
•  

설명

최단 경로 count 변수를 갱신하기 위해, 레벨별로 bfs를 진행하였다.

각 레벨의 위치값의 nx, ny를 구하여 유효하면 bfsQueue에 값을 저장한다.

해당 레벨을 다 돌았으면 count 변수를 갱신시켜준다.

구현

from collections import deque

n = int(input())
m = int(input())
inputMap = [[-1 for _ in range(m)] for _ in range(n)]

for i in range(n):
    inputRow = list(map(int,input().split(' ')))
    for j in range(m):
        inputMap[i][j] = inputRow[j]

def bfs(inputMap,n,m):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    bfsQueue = deque()
    bfsQueue.append((0,0))
    cnt = 1

    while bfsQueue:
        # 최단 경로를 세기 위한 레벨별 탐색
        for _ in range(len(bfsQueue)):
            x,y = bfsQueue.popleft()

            if x==m-1 and y==n-1: return cnt
            if inputMap[y][x]!=1: continue

            inputMap[y][x] = 0  # 방문 표시

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= m or ny >= n or inputMap[ny][nx]!=1:
                    continue
                bfsQueue.append((nx,ny))
        cnt += 1 
        

print(bfs(inputMap,n,m))