백준 1913번 (C++) 달팽이

https://www.acmicpc.net/problem/1913

1913번: 달팽이

 

 

정-직하게 2차원 배열의 가운데부터 1씩 증가하며

달팽이 모양(상, 우, 하, 좌) 순으로 2차원 배열을 탐색했다.

 

 

내가 이미 채운 곳이라면 (이미 어떤 cnt라는 정수가 채워져 0이 아니라면)

왔던 방향을 한번 더 가면된다. 

 

 

이는 곧 현재의 방향을 나타내는 iterator i를 2 감소하면 된다.

1을 감소하면 되는게 맞지만,

현재 내가 수행한 반복문의 끝에서 1이 증가하므로 그것까지 고려해 2를 감소한다.

 

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int N, M;
    cin >> N >> M;
    
    vector<vector<int>> v(N, vector<int>(N, 0));
    
    int x = (N - 1) / 2;
    int y = x;
    int cnt = 1;
    
    v[x][y] = cnt++;
    while (cnt <= N*N) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
                continue;
            }
            if (v[nx][ny] != 0) {
                if (i == 0) i = 2;
                else if (i == 1) i = 3;
                else i-=2;
            }
            else {
                v[nx][ny] = cnt++;
                x = nx; y = ny;
            }
        }
    }
    int ans_x, ans_y;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << v[i][j] << " ";
            if (v[i][j] == M) {
                ans_x = i+1; ans_y = j+1;
            }
        }
        cout << endl;
    }
    cout << ans_x << " " << ans_y;
    return 0;
}