문제를 푸는 기준

격자의 칸을 정점, 이동 가능한 인접 칸을 간선으로 봅니다. 최소 이동 횟수는 BFS, 연결 영역은 DFS나 BFS로 해결합니다.

핵심 개념

대표 문제

격자 최단 이동 거리

0은 이동 가능, 1은 벽인 grid에서 왼쪽 위부터 오른쪽 아래까지 상하좌우 최소 이동 횟수를 반환하세요. 도달할 수 없으면 -1입니다.

함수 시그니처: solution(grid)

제한사항

• 행과 열의 길이는 각각 1 이상 500 이하입니다.
• 시작 칸과 도착 칸도 벽일 수 있습니다.

입출력 예

풀이 설계

1. 거리 배열을 -1로 채우고 시작 거리를 0으로 둡니다.
2. 큐에서 칸을 꺼내 상하좌우를 확인합니다.
3. 처음 발견한 칸에 현재 거리보다 1 큰 값을 기록합니다.

JavaScript 풀이

function solution(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  if (grid[0][0] === 1 || grid[rows - 1][cols - 1] === 1) return -1;
  const distance = Array.from({ length: rows }, () => Array(cols).fill(-1));
  const queue = [[0, 0]];
  const directions = [[1,0],[-1,0],[0,1],[0,-1]];
  let head = 0;
  distance[0][0] = 0;
 
  while (head < queue.length) {
    const [row, col] = queue[head++];
    for (const [dr, dc] of directions) {
      const nr = row + dr;
      const nc = col + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (grid[nr][nc] === 1 || distance[nr][nc] !== -1) continue;
      distance[nr][nc] = distance[row][col] + 1;
      queue.push([nr, nc]);
    }
  }
  return distance[rows - 1][cols - 1];
}

복잡도

• 시간복잡도: O(R × C)
• 공간복잡도: O(R × C)
• 핵심 패턴: BFS에서 발견 즉시 방문 거리 기록
• 경계 사례: 시작 또는 도착이 벽이면 -1 반환

연습 문제

1. 섬 개수

1로 연결된 영역 개수를 반환하세요.

2. 영역 넓이

연결 영역의 최대 칸 수를 반환하세요.

3. 다중 시작 확산

여러 시작점의 최소 확산 시간을 구하세요.

자주 하는 실수

• 큐에서 꺼낼 때 방문 표시해 중복 삽입하는 실수
• 행과 열 경계를 반대로 비교하는 실수
• shift를 반복하는 실수
• 가중치가 다른 간선에 BFS를 적용하는 실수

핵심 정리

• 함수 시그니처와 반환 자료형을 먼저 확정합니다.
• 제한사항으로 가능한 시간복잡도를 판단합니다.
• 예시와 경계 사례를 손으로 추적한 뒤 구현합니다.
• 완성한 solution 함수가 입력을 불필요하게 바꾸지 않는지도 확인합니다.

확인 문제

참고 자료

• Princeton Algorithms 4e - Graphs 
• MIT OpenCourseWare 6.006 Introduction to Algorithms 
• 프로그래머스 코딩테스트 고득점 Kit