Graphs - BFS

Graphs - BFS

---

BFS와 DFS 비교

트리 문제와 마찬가지로, 많은 그래프 문제에서도 DFS(깊이 우선 탐색)이나 BFS(너비 우선 탐색) 중 어느 것을 사용해도 상관없는 경우가 많습니다. DFS가 BFS 보다 더 나은 성능을 보이는 상황은 드뭅니다. 사람들이 DFS를 선택하는 주된 이유는 DFS가 특히 재귀적으로 구현할 때 더 빠르고 코드가 간결하기 때문입니다.

그러나, 특정 문제에서는 BFS가 더 적합한 경우가 있습니다. 트리에서는 레벨(Level)에 관련된 문제에서 BFS가 유리했듯, 그래프에서는 최단 경로 를 찾는 문제에서 BFS가 더 적합합니다.

BFS의 핵심

BFS는 시작점에서의 거리에 따라 노드를 방문합니다. 트리에서는 BFS가 특정 깊이(d)에 속한 모든 노드를 방문한 후, 그 다음 깊이(d+1)의 노드를 방문합니다. 이와 동일한 로직이 그래프에도 적용됩니다. BFS는 그래프에서도 시작점에서 특정 노드까지 도달하는 최소 단계를 보장합니다.

• 트리에서는 루트(root)에서 각 노드까지 단 하나의 경로만 존재하지만, 그래프에서는 여러 경로가 있을 수 있습니다.
• BFS 는 여러 경로 중에서 가장 짧은 경로를 선택합니다.

BFS 와 DFS 의 구현 차이

• DFS는 주로 재귀를 사용하며, 내부적으로도 스택을 활용합니다.
• BFS는 반복(iterative)방식으로 구현되며, Queue를 사용합니다.

---

Ex 1. Binary Matrix 에서 최단 경로 찾기

문제 설명

n x n 크기의 이진 행렬 grid가 주어집니다.

• 목표 : (0, 0)에서 (n-1, n-1)까지의 최단 경로 길이를 반환하세요.
• 조건
  • 0은 통과할 수 있는 칸, 1은 통과할 수 없는 칸을 의미합니다.
  • 이동은 상하좌우 및 대각선 방향으로 가능합니다.
  • 경로가 없으면 -1을 반환합니다.

BFS를 사용하는 이유

• DFS로 풀 경우, 경로가 최단 경로가 아닐 가능성이 있습니다.
• BFS는 방문하는 각 노드가 시작점에서 최소 단계로 도달한 것임을 보장합니다.

BFS 구현 과정

1. queue에 시작점을 추가합니다.

- (x, y) 좌표와 현재까지의 단계 step 를 저장합니다.
- 초기 상태로 (0, 0, 1) 을 큐에 추가합니다. 여기서 1은 첫번째 단계.

2. 유효성 검사

• 이동하려는 좌표가 행렬 범위 안에 있는지 확인합니다.
• 해당 칸이 이미 방문되었는지 확인합니다.

3. BFS 탐색

• 큐에서 노드를 하나 꺼냅니다.
• 인접한 모든 칸(8방향 - 상하좌우/대각선)에 대해 다음을 수행
  - 이동 가능한 칸이면 큐에 (nx, ny, steps + 1) 을 추가합니다.
  • 목표 칸 (n-1, n-1) 에 도달하면 해당 steps 를 반환합니다.

4. 결과 반환

• 큐가 비었음에도 목표에 도달하지 못했다면, 경로가 없으므로 -1 을 반환합니다.

---

시간 복잡도와 공간 복잡도

시간 복잡도

• BFS는 각 노드를 최대 한 번 방문하므로, 노드의 개수에 비례합니다: 𝑂(𝑛^2)

공간 복잡도

• 큐와 방문 여부를 저장하는 배열의 크기 역시 𝑂(𝑛^2)입니다.

---

구현 요약

유효성 검사 함수:

• 이동 가능한지 확인합니다.
• 유효하지 않은 칸을 제외합니다.

방문 여부 배열:

• 중복 탐색을 방지합니다.

큐를 이용한 탐색:

• BFS는 각 레벨(단계)을 큐로 관리하며 탐색을 진행합니다.

결과 반환:

• 첫 번째로 (n-1, n-1)에 도달한 단계 수를 반환합니다.

---

data class State(val row: Int, val col: Int, val steps: Int)

class Solution {
    private lateinit var grid: Array<IntArray>
    private val directions = arrayOf(
        intArrayOf(-1, -1), intArrayOf(-1, 0), intArrayOf(-1, 1),
        intArrayOf(0, -1),                    intArrayOf(0, 1),
        intArrayOf(1, -1), intArrayOf(1, 0), intArrayOf(1, 1)
    )
    
    fun shortestPathBinaryMatrix(grid: Array<IntArray>): Int {
        if (grid[0][0] == 1) return -1 // 시작 지점이 장애물일 경우 -1 반환

        val n = grid.size
        val seen = Array(n) { BooleanArray(n) } // 방문 여부를 저장하는 배열
        val queue: Queue<State> = LinkedList() // BFS 큐
        queue.add(State(0, 0, 1)) // 시작점 추가
        seen[0][0] = true // 시작점 방문 표시

        while (queue.isNotEmpty()) {
            val (row, col, steps) = queue.poll()

            // 목표 지점 도달 시 현재 단계 반환
            if (row == n - 1 && col == n - 1) return steps

            // 8방향으로 이동
            for (direction in directions) {
                val nextRow = row + direction[0]
                val nextCol = col + direction[1]

                // 유효한 위치인지 확인
                if (isValid(nextRow, nextCol, n) && grid[nextRow][nextCol] == 0 && !seen[nextRow][nextCol]) {
                    seen[nextRow][nextCol] = true // 방문 표시
                    queue.add(State(nextRow, nextCol, steps + 1)) // 다음 위치 추가
                }
            }
        }

        return -1 // 목표에 도달할 수 없는 경우
    }

    private fun isValid(row: Int, col: Int, n: Int): Boolean {
        return row in 0 until n && col in 0 until n
    }
}

1. State Class

data class State(val row: Int, val col: Int, val steps: Int)

• row: 현재 행
• col: 현재 열
• steps: 시작점에서 현재 위치까지 도달하는 데 소요된 단계 수

2. 방향 배열 (directions)

이동 가능한 8방향(상하좌우 및 대각선)을 정의합니다.

private val directions = arrayOf(
        intArrayOf(-1, -1), intArrayOf(-1, 0), intArrayOf(-1, 1),
        intArrayOf(0, -1),                    intArrayOf(0, 1),
        intArrayOf(1, -1), intArrayOf(1, 0), intArrayOf(1, 1)
    )

• 각 원소는 intArrayOf(변화행, 변화열) 형태로 구성됩니다.
• (변화행, 변화열) 은 현재 위치 (row, col) 에서 다음 위치를 계산할 때 사용됩니다.

val newRow = row + 변화_행
val newCol = col + 변화_열

각 방향의 의미

그리드는 2D 좌표 평면처럼 행(row)와 열(column)로 구성됩니다.

• 행(row) : 위에서 아래로 증가 (-1은 위로, 1은 아래로 이동)
• 열(column): 왼쪽에서 오른쪽으로 증가 (-1은 왼쪽으로, 1은 오른쪽으로 이동).

시각적 이해

 ↖  ↑  ↗
 ←  ●  →
 ↙  ↓  ↘

• ↖: (-1, -1) (왼쪽 위)
  ↑: (-1, 0) (위쪽)
  ↗: (-1, 1) (오른쪽 위)
  ←: (0, -1) (왼쪽)
  →: (0, 1) (오른쪽)
  ↙: (1, -1) (왼쪽 아래)
  ↓: (1, 0) (아래쪽)
  ↘: (1, 1) (오른쪽 아래)

---

좌표계의 기준

1. (0, 0):

- 가장 왼쪽 위의 셀을 기준으로 잡습니다.
- 즉, **행(row)**은 위에서 아래로 증가하고, **열(column)**은 왼쪽에서 오른쪽으로 증가합니다.

2. 행(row):

	- 위쪽으로 이동 → 행 감소 → -1
	- 아래쪽으로 이동 → 행 증가 → +1

3. 열(column):

	- 왼쪽으로 이동 → 열 감소 → -1
	- 오른쪽으로 이동 → 열 증가 → +1

---

왜 (0, 0)이 왼쪽 위인가?

이는 컴퓨터 그래픽스와 많은 프로그래밍 언어에서 사용하는 일반적인 2D 좌표계 관습 때문입니다

• 행렬, 배열, 또는 이미지를 다룰 때 왼쪽 위를 (0, 0)으로 시작하는 경우가 많습니다.
• 이는 메모리 배치 방식과도 관련이 있습니다.
  • 배열의 첫 번째 원소가 (0, 0)으로, 그 다음 행(row)이 증가하면서 메모리에 저장됩니다.

시각적으로 표현

(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)

---

예제 코드로 다시 돌아오면,

3. shortestPathBinaryMatrix 함수

fun shortestPathBinaryMatrix(grid: Array<IntArray>): Int {
        if (grid[0][0] == 1) return -1 // 시작 지점이 장애물일 경우 -1 반환

        val n = grid.size
        val seen = Array(n) { BooleanArray(n) } // 방문 여부를 저장하는 배열
        val queue: Queue<State> = LinkedList() // BFS 큐
        queue.add(State(0, 0, 1)) // 시작점 추가
        seen[0][0] = true // 시작점 방문 표시

        while (queue.isNotEmpty()) {
            val (row, col, steps) = queue.poll()

            // 목표 지점 도달 시 현재 단계 반환
            if (row == n - 1 && col == n - 1) return steps

            // 8방향으로 이동
            for (direction in directions) {
                val nextRow = row + direction[0]
                val nextCol = col + direction[1]

                // 유효한 위치인지 확인
                if (isValid(nextRow, nextCol, n) && grid[nextRow][nextCol] == 0 && !seen[nextRow][nextCol]) {
                    seen[nextRow][nextCol] = true // 방문 표시
                    queue.add(State(nextRow, nextCol, steps + 1)) // 다음 위치 추가
                }
            }
        }

        return -1 // 목표에 도달할 수 없는 경우
    }

• 입력 : 2D 이진 행렬 grid
• 출력 : 최단 경로 길이, 없으면 -1

주요 흐름

• 초기 검사
  - 시작점 (0,0) 이 1(장애물)일 경우, 바로 -1 반환

• 초기화
  - seen 배열 : 방문 여부를 저장
  - queue : BFS 큐에 시작점과 초기 단계 수 (1) 을 추가

• BFS 탐색
  - 큐가 빌 때까지 반복
  - 현재 노드를 꺼내고, 8방향으로 탐색

  • 유효한 위치인지 확인(isValid 함수 사용)
  • 장애물 (값이 1)이 아니고, 아직 방문하지 않았다면
    • 방문 표시
      • 다음 상태(steps + 1)

• 목표 지점 (n-1,n-1)에 도달하면 즉시 steps 반환.

• 큐가 비었는데도 목표 지점에 도달하지 못하면 -1 반환.

4. isValid() 함수

private fun isValid(row: Int, col: Int, n: Int): Boolean {
        return row in 0 until n && col in 0 until n
    }

• 주어진 좌표가 행렬의 범위 내에 있는지 확인합니다.