[백준] 1913. 달팽이 - C++

문제

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

 

• 소요 시간 : 30분
• 난이도 : 실버 3

접근 방법

1. (0, 0) 부터  N^2의 수를 역순으로 1까지 채워나간다.

2. 방향은 하, 우, 상, 좌를 번갈아서 채운다.

방향을 바꾸는 시점은 아래 2가지이다. 

- x, y가 0보다 작거나 N과 같을 경우

- 가려는 곳에 이미 숫자가 채워져있을 경우 

나의 풀이

#include <iostream>
#include <cmath>

using namespace std;

int map[1000][1000];
int N, X;

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

int main() {

    cin >> N;
    cin >> X;

    int dirIdx = 0, x = 0, y = 0;
    int num = pow(N, 2);

    int ny, nx;

    while(num > 0) {
        // 채워 넣기
        map[y][x] = num;

        num--;      

        ny = y + dy[dirIdx];
        nx = x + dx[dirIdx];

        // 벽에 부딛히거나 이미 숫자가 존재한다면 방향 전환
        if (ny < 0 || ny >= N || nx < 0 || nx >= N || map[ny][nx]) {
            dirIdx = (dirIdx + 1) % 4; 
        }

        y = y + dy[dirIdx];
        x = x + dx[dirIdx];
    }

    int answerX, answerY;

    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cout << map[i][j] << " ";

            if (map[i][j] == X) {
                answerY = i + 1;
                answerX = j + 1;
            }

        }
        cout << "\n";
    }

    cout << answerY << " " << answerX << "\n";

    return 0;
}

정리

코테에서 비슷한 유형의 문제가 나왔던 것 같다. 재밌는 문제~