### 좌표와 거리표를 따로 담아요 이번에는 2차원 vector·조건·반복·큐를 사용해 격자의 최단거리를 구해요. ``의 `queue`는 먼저 넣은 항목부터 읽는 FIFO예요. `push`로 넣고 `front`로 읽은 다음 `pop`으로 지워요. 격자의 `(r,c)`는 r행 c열이고, 상하좌우 이동만 허용해요. 행 범위는 0≤r> dist(rows, vector(cols, -1));`은 −1인 칸 cols개를 가진 행을 rows개 만들어요. --- ### 먼저 넣은 가까운 칸부터 꺼내요 시작 칸을 큐에 넣어요. 칸을 하나 꺼낸 뒤, 격자 안에 있고 막히지 않았고 아직 거리 −1인 이웃만 큐에 넣어요. 이웃의 거리는 현재 거리+1이에요. 거리 기록은 큐에 넣을 때 해요. ```cpp queue> pending; pending.push({0, 0}); vector 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인 칸들은 그 뒤에 들어가요. --- ### 이동 방향 네 개를 같은 규칙으로 검사해요 ```cpp vector dr = {-1, 1, 0, 0}; vector 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이에요.

로그인