프로그래머스 정수를 나선형으로 배치하기 문제 바로가기

아니 이게 Lv.0 문제라고?! DFS에 나올법한 꽤나 난이도 있는 문제였다. 일일히 구현하는것도 쉬운 문제는 아니었다. 예전에 python에서 graph관련 알고리즘 문제를 풀었던 기억이 있어서 C++로도 풀이해보았다.

내 풀이

  1. dx, dy를 vector로 지정해서 다음 움직임의 방향을 지정해주었다. mode에 따라서 dx[mode]처럼 불러와서 다음 위치를 알아낼 수 있다.
  2. 다음 위치에 이미 부여한 숫자가 있거나(0이 아니거나), 주어진 범위에 넘어가면 안되기에 예외 처리를 해주었다.
  3. 알맞게 구현한 것 같은데 자꾸만 segmentation fault 오류가 발생해서 알아보니 mode가 4를 넘어가면 dx,dy의 index를 초과하기에 발생하는 에러였다. 따라서 mode를 4로 나눈 나머지로 (mod 4) 설정하면 오류에서 벗어날 수 있다.
#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> solution(int n) {
    vector<vector<int>> answer(n, vector<int>(n, 0));
    vector<int> dx = {1,0,-1,0};
    vector<int> dy = {0,1,0,-1};
    int x=0;
    int y=0;
    int mode = 0;
    
    for (int i=1; i<=n*n; i++){
        answer[y][x] = i;
        int x_next = x+dx[mode];
        int y_next = y+dy[mode];
        bool a = (x_next<0 || x_next>=n);
        bool b = (y_next<0 || y_next>=n);
        bool c = (answer[y_next][x_next] != 0);
        
        if (a || b || c){
            mode = (mode + 1)%4;
        };
        
        x += dx[mode];
        y += dy[mode];
    }
    return answer;
}