{}연습장
대시보드학습스킬 경로문제모의고사라이브 코테복습데이터
문제 목록〉BFS/DFS〉창고 로봇 최단 이동 칸 수← 이전다음 →
#035 · BFS/DFS중간격자 BFS,최단 경로

창고 로봇 최단 이동 칸 수

문제

물류 창고 바닥은 격자로 나뉘어 있습니다. warehouse[r][c]가 1이면 로봇이 지나갈 수 있는 통로, 0이면 적재물이 놓여 있어 지나갈 수 없는 칸입니다.

로봇은 상하좌우 네 방향으로 한 칸씩 이동하며, 대각선으로는 움직일 수 없습니다.

출발 칸 start = [행, 열]과 목표 칸 goal = [행, 열]이 주어질 때, 로봇이 목표 칸에 도착하기까지 지나는 칸의 개수(출발 칸과 목표 칸을 모두 포함)의 최솟값을 반환하는 solution(warehouse, start, goal) 함수를 작성하세요. 목표 칸에 도달할 수 없으면 -1을 반환합니다.

출발 칸과 목표 칸이 같으면 답은 1입니다.

예시

창고가 다음과 같을 때(5행 6열),

1 1 0 1 1 1
0 1 0 1 0 1
1 1 1 1 0 1
1 0 0 1 1 1
1 1 1 1 0 1
start goal 결과
[0, 0] [4, 5] 10
[2, 0] [0, 5] 8
[0, 0] [0, 0] 1

예시 1 설명: (0,0) → (0,1) → (1,1) → (2,1) → (2,2) → (2,3) → (3,3) → (3,4) → (3,5) → (4,5)로 10칸을 지납니다.

예시 2 설명: (2,0) → (2,1) → (2,2) → (2,3) → (1,3) → (0,3) → (0,4) → (0,5)로 8칸입니다.

막힌 창고의 예로, warehouse = [[1, 0], [0, 1]]에서 start = [0, 0], goal = [1, 1]이면 두 통로가 대각선으로만 닿아 있어 -1입니다.

제약 조건

  • 1 ≤ warehouse.length, warehouse[0].length ≤ 100
  • warehouse[r][c]는 0 또는 1
  • start와 goal은 항상 격자 안의 좌표이며, 두 칸의 값은 항상 1입니다.
  • 모든 행의 길이는 같습니다.

시간 복잡도 목표: O(행 × 열)

공간 복잡도 목표: O(행 × 열)

테스트 케이스

예시 1: 좌상단 → 우하단, 10칸
입력: warehouse = [[1,1,0,1,1,1],[0,1,0,1,0,1],[1,1,1,1,0,1],[1,0,0,1,1,1],[1,1,1,1,0,1]], start = [0,0], goal = [4,5]
출력: 10
예시 2: 중간 왼쪽 → 우상단, 8칸
입력: warehouse = [[1,1,0,1,1,1],[0,1,0,1,0,1],[1,1,1,1,0,1],[1,0,0,1,1,1],[1,1,1,1,0,1]], start = [2,0], goal = [0,5]
출력: 8
예시 3: 출발 = 목표 → 1
입력: warehouse = [[1,1,0,1,1,1],[0,1,0,1,0,1],[1,1,1,1,0,1],[1,0,0,1,1,1],[1,1,1,1,0,1]], start = [0,0], goal = [0,0]
출력: 1
엣지: 대각선으로만 닿아 도달 불가
입력: warehouse = [[1,0],[0,1]], start = [0,0], goal = [1,1]
출력: -1
엣지: ㄷ자로 우회, 7칸
입력: warehouse = [[1,1,1],[0,0,1],[1,1,1]], start = [0,0], goal = [2,0]
출력: 7
엣지: 1×1 창고
입력: warehouse = [[1]], start = [0,0], goal = [0,0]
출력: 1
solution.ts
에디터 로딩 중…

▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.