막힌 칸을 피해 도착하기

좌표와 거리표를 따로 담아요

이번에는 2차원 vector·조건·반복·큐를 사용해 격자의 최단거리를 구해요. <queue>의 queue는 먼저 넣은 항목부터 읽는 FIFO예요. push로 넣고 front로 읽은 다음 pop으로 지워요.

격자의 (r,c)는 r행 c열이고, 상하좌우 이동만 허용해요. 행 범위는 0≤r<rows, 열 범위는 0≤c<cols예요. 칸 안의 장애물 값과, 그 칸까지 이동한 횟수는 다른 정보이므로 거리표 dist를 별도로 만들어요. 아직 도착하지 않은 칸에는 −1을 기록해요. 시작 칸의 거리는 0이에요. vector<vector<int>> dist(rows, vector<int>(cols, -1));은 −1인 칸 cols개를 가진 행을 rows개 만들어요.

먼저 넣은 가까운 칸부터 꺼내요

시작 칸을 큐에 넣어요. 칸을 하나 꺼낸 뒤, 격자 안에 있고 막히지 않았고 아직 거리 −1인 이웃만 큐에 넣어요. 이웃의 거리는 현재 거리+1이에요. 거리 기록은 큐에 넣을 때 해요.

queue<vector<int>> pending;
pending.push({0, 0});
vector<int> current = pending.front();
pending.pop();

큐의 한 원소 {r,c}는 좌표 두 개를 담은 vector예요. current[0]은 행, current[1]은 열이에요. dist를 확인하므로 같은 칸을 중복해서 넣지 않아요.

벽 없는 2×3 격자에서 거리 0의 (0,0)을 꺼내면 (1,0)과 (0,1)에 거리 1을 기록해요. 그다음 (1,0)을 꺼내도 아직 큐 앞쪽에 거리 1의 (0,1)이 남아 있어요. 거리 2인 칸들은 그 뒤에 들어가요.

이동 방향 네 개를 같은 규칙으로 검사해요

vector<int> dr = {-1, 1, 0, 0};
vector<int> dc = {0, 0, -1, 1};

탐색 코드에서 ||는 어느 하나라도 참, &&는 둘 다 참, !는 참·거짓을 반대로 바꾸는 연산자예요. while (!pending.empty())는 큐가 비지 않은 동안 반복해요. continue;는 현재 방향 검사를 끝내고 다음 방향으로 넘어가요. 예를 들어 격자 밖 좌표라면 거리표를 읽지 않고 건너뛰어요.

같은 인덱스의 dr·dc를 한 쌍으로 써요. 0번은 위, 1번은 아래, 2번은 왼쪽, 3번은 오른쪽이에요. 새 좌표는 nr=r+dr[d], nc=c+dc[d]예요.

벽 없는 2×3 격자에서 마지막 칸 (1,2)의 거리는 얼마일까요? 상하좌우로 세 번 이동한 3이에요. 큐가 빌 때까지 끝 칸에 도착하지 못하면 거리 −1이 그대로 남아요. 시작과 끝이 같은 1×1 격자는 이동하지 않아 거리 0이에요.

직접 풀어봐요

격자 grid에서 (0,0)부터 (rows−1,cols−1)까지 상하좌우로 이동해요. 0은 지나갈 수 있고 1은 막힌 칸이에요. 한 번 이동할 때 이웃한 칸 하나로 가요. 필요한 최소 이동 횟수를 반환하고, 도착할 수 없으면 −1을 반환해요. 시작 칸에 서 있는 것은 이동 횟수에 포함하지 않아요.

행 수와 열 수는 각각 1~20이고 모든 행의 길이는 같아요. 원소는 0 또는 1이에요. 시작 칸과 끝 칸은 항상 0이에요. 실행용 입력은 첫 줄 rows cols, 다음 rows줄에 각 행의 cols개 정수예요. 출력은 반환값이에요. 하네스가 입력·출력을 처리해요.

예시 1: {{0,0,0},{1,1,0},{0,0,0}} → 4. 오른쪽 두 번, 아래 두 번 이동해요. 예시 2: {{0,1,0},{0,1,0},{0,1,0}} → -1. 가운데 벽을 통과할 수 없어 오른쪽 끝에 도착하지 못해요.

3 3
0 0 0
1 1 0
0 0 0

4

3 3
0 1 0
0 1 0
0 1 0

-1