격자(2D 배열) 탐색 완전 템플릿: 상하좌우 + 대각선 + DFS/BFS

2차원 격자(배열) 문제에서 자주 쓰이는 상하좌우 및 대각선 방향 탐색 코드의 템플릿입니다.

---

✅ 격자 배열 초기화

const grid = Array.from({ length: N }, () => Array(M).fill(0));
const visited = Array.from({ length: N }, () => Array(M).fill(0));

• N: 행 개수 (row)
• M: 열 개수 (column)
• grid: 문제에서 주어지는 맵/지도/판
• visited: 탐색 여부 저장용 (0/1 or true/false)
  

---

🔁 기본 방향 벡터 정의 (상하좌우)

const dx = [0, 0, -1, 1]; // 좌우
const dy = [-1, 1, 0, 0]; // 상하

각 인덱스는 다음 방향을 의미합니다:

i	방향	dy[i]	dx[i]	이동 결과
0	위	-1	0	(y - 1, x)
1	아래	+1	0	(y + 1, x)
2	왼쪽	0	-1	(y, x - 1)
3	오른쪽	0	+1	(y, x + 1)

---

🔀 8방향 탐색 (상하좌우 + 대각선)

const dx8 = [0, 0, -1, 1, -1, -1, 1, 1];
const dy8 = [-1, 1, 0, 0, -1, 1, -1, 1];

방향	설명
상하좌우	기본 4방향
대각선	↖ ↗ ↙ ↘

---

🧩 재귀 DFS 템플릿 (4방향)

function dfs(y: number, x: number) {
  visited[y][x] = 1;

  for (let i = 0; i < 4; i++) {
    const ny = y + dy[i];
    const nx = x + dx[i];

    if (ny >= 0 && ny < N && nx >= 0 && nx < M) {
      if (grid[ny][nx] === 조건 && !visited[ny][nx]) {
        dfs(ny, nx);
      }
    }
  }
}

• 간단하고 직관적이며, 소규모 입력에 적합
• 재귀 깊이가 깊어질 경우 JS에서는 stack overflow 위험 있음

---

🧩 반복 DFS (스택 기반) 템플릿 (4방향)

function dfsIterative(startY: number, startX: number) {
  const stack = [[startY, startX]];  // 스택 초기화: 시작 좌표 삽입
  visited[startY][startX] = 1;       // 시작 위치 방문 처리

  while (stack.length > 0) {         // 스택이 빌 때까지 반복
    const [y, x] = stack.pop()!;     // 현재 좌표 꺼냄 (탐색 시작점)

    for (let i = 0; i < 4; i++) {    // 상하좌우 네 방향 탐색
      const ny = y + dy[i];          // 새 y좌표
      const nx = x + dx[i];          // 새 x좌표

      if (ny >= 0 && ny < N && nx >= 0 && nx < M) {  // 범위 안에 있고
        if (grid[ny][nx] === 조건 && !visited[ny][nx]) {
          visited[ny][nx] = 1;      // 방문 표시
          stack.push([ny, nx]);     // 스택에 넣어서 다음 탐색 준비
        }
      }
    }
  }
}

• 재귀 대신 직접 스택을 사용하여 깊이 우선 탐색 구현
• 대규모 입력에서도 안전하며, 실전에서 매우 안정적

---

🧩 BFS (큐 기반) 템플릿 (4방향)

function bfs(startY: number, startX: number) {
  const queue = [[startY, startX]];
  visited[startY][startX] = 1;

  while (queue.length > 0) {
    const [y, x] = queue.shift()!;

    for (let i = 0; i < 4; i++) {
      const ny = y + dy[i];
      const nx = x + dx[i];

      if (ny >= 0 && ny < N && nx >= 0 && nx < M) {
        if (grid[ny][nx] === 조건 && !visited[ny][nx]) {
          visited[ny][nx] = 1;
          queue.push([ny, nx]);
        }
      }
    }
  }
}

• 너비 우선 탐색 (최단 거리 문제에 적합)
• 큐 사용 시 자바스크립트의 shift()가 느릴 수 있으므로 유의

---

🧩 8방향 탐색으로 바꾸기

위의 DFS/BFS에서 dy, dx를 dy8, dx8로 바꾸면 대각선까지 포함한 탐색이 가능:

for (let i = 0; i < 8; i++) {
  const ny = y + dy8[i];
  const nx = x + dx8[i];
  // 동일한 조건으로 탐색
}

---

🧩 적용 가능한 문제 유형

• DFS/BFS로 영역 구분 (섬의 개수, 단지 번호 붙이기)
• 미로 탐색 / 최단 거리
• 퍼지는 것 (불, 전염병, 확산 등)
• flood fill (색칠, 연결된 영역 칠하기)
• 땅 고르기, 빙산, 단절 여부 등

---

📝 요약

• dy, dx를 통해 간단하고 일관된 방향 탐색이 가능함
• 2차원 격자에서 반복적으로 사용되므로 암기 수준으로 숙지 필요
• 실전에서는 visited 배열과 함께 활용하여 중복 탐색을 방지
• 8방향 탐색은 대각선 연결도 확인해야 하는 문제에서 활용