R행 C열로 이루어진 2차원 격자가 있다고 가정해 보겠습니다. 우리는 (r0, c0) 위치에서 동쪽을 향해 출발하며, 격자의 북서쪽 모서리는 첫 번째 행과 열에, 남동쪽 모서리는 마지막 행과 열에 위치합니다. 이때 시계 방향의 나선형 경로를 따라 이동하면서 격자의 모든 칸을 방문해야 합니다. 도중에 격자 경계를 벗어나더라도 걸음을 멈추지 않고 계속 진행하며(이후 다시 격자 안으로 돌아올 수 있습니다), 방문한 순서대로 좌표 목록을 만들면 됩니다.
예를 들어 격자가 아래와 같다면 −
화살표가 표시하는 경로가 곧 우리가 따라가야 할 이동 순서입니다.
이 문제는 다음 단계를 통해 해결할 수 있습니다 −
방향 배열 dirr := [[0,1],[1,0],[0,-1],[-1,0]]을 생성합니다. 각 원소는 순서대로 동쪽, 남쪽, 서쪽, 북쪽을 의미합니다.
결과를 저장할 행렬 ret을 만들고, len := 0, dir := 0으로 초기화합니다.
시작 위치 (r0, c0)를 ret에 삽입합니다.
ret의 크기가 R×C보다 작은 동안 다음 과정을 반복합니다.
dir이 0(동쪽) 또는 2(서쪽)일 때 len을 1만큼 증가시킵니다. 나선형 경로에서는 수평 이동이 한 번씩 끝날 때마다 한 변의 길이가 1씩 늘어나기 때문입니다.
i를 0부터 len – 1까지 반복하면서 다음을 수행합니다.
r0 := r0 + dirr[dir][0], c0 := c0 + dirr[dir][1]로 현재 위치를 한 칸 이동합니다.
r0가 0 ~ R−1 범위를 벗어나거나 c0가 0 ~ C−1 범위를 벗어나면 해당 좌표는 기록하지 않고 다음 반복으로 건너뜁니다.
격자 범위 안에 있는 좌표라면 (r0, c0)를 ret에 삽입합니다.
dir := (dir + 1) mod 4로 방향을 시계 방향으로 전환합니다.
모든 칸을 방문했다면 ret을 반환합니다.
이 방식의 장점은 격자 크기와 시작 위치에 관계없이 경계를 벗어나는 구간을 자연스럽게 처리하면서도, 격자 내부에 있는 좌표만 결과에 담을 수 있다는 점입니다. 아래 구현 예시를 통해 더 자세히 이해해 보겠습니다 −
예제
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
int dirr[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
class Solution {
public:
vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
vector < vector <int> > ret;
int len = 0;
int dir = 0;
ret.push_back({r0, c0});
while(ret.size() < R * C){
if(dir == 0 || dir == 2) len++;
for(int i = 0; i < len; i++){
r0 = r0 + dirr[dir][0];
c0 = c0 + dirr[dir][1];
if(r0 < 0 || c0 < 0 || c0 >= C || r0 >= R) continue;
ret.push_back({r0, c0});
}
dir = (dir + 1) % 4;
}
return ret;
}
};
main(){
Solution ob;
print_vector(ob.spiralMatrixIII(5,5,1,3));
}
입력
5 5 1 3
출력
[[1,3],[1,4],[2,4],[2,3],[2,2],[1,2],[0,2],[0,3],[0,4],[3,4],[3,3],[3,2],[3,1],[2,1],[1,1],[0,1],[4,4],[4,3],[4,2],[4,1],[4,0],[3,0],[2,0],[1,0],[0,0]]