깃허브 링크
문제
백준/BOJ - 1913. 달팽이
프로그래머스 - 삼각 달팽이
문제 풀이
달팽이 배열
달팽이 배열은 나선형으로 숫자가 채워진 배열입니다.
저는 프로그래밍 공부를 시작할 때 달팽이 배열을 구현하는 문제를 처음 접한 경험이 있는데요, 그때 어디서부터 어떻게 배열을 채워나가야 할지 되게 난감했었습니다. 그때는 하드코딩으로 많은 예외처리를 하며 풀었었는데.
현재 제가 푼 방법은 배열 진행 방향에 따라 숫자를 증감하는 방식입니다.
크게,
현재 진행 방향으로 이동할 칸의 수만큼 배열을 이동하며 숫자를 넣습니다.
그리고 이동할 칸의 수만큼 이동을 하게 되면, 진행 방향을 바꿔줍니다.
의사 코드로 구현해봅시다.
배열의 진행 방향 열거형을 정의합니다.
// 사각형 달팽이 배열의 경우 이동할 수 있는 방향은 오른쪽, 왼쪽, 위, 아래입니다.
enum class Direction
{
Right, Left, Up, Down
};필요한 변수들을 정의합니다.
// 가로, 세로 칸수
int n ;
// 최대 수
const int MAX_NUM = n*n;
// 현재 배열에 채워질 숫자
int num = n;
// 현재 진행 방향 (처음에는 아래로 방향이 진행됩니다)
Direction direction = Direction::Down;
// 현재 채워져아 하는 칸 수
int step = N;
// 진행 시작될 때 row, column 인덱스
int row_index = -1;
int column_index = 0;
이미지와 같은 방향으로 배열을 채워보겠습니다. 한 방향으로 진행되지 않기 때문에 방향에 따라서, row, column이 지정되는 부분이 중요합니다.
제가 중요하다고 생각하는 부분은
1. 진행 방향에 따라, row, column을 지정하는 부분
2. 특정 방향으로 진행할 때, 이동해야하는 칸 수를 지정하는 부분
// n이 1이 될 때까지 배열 채워넣기를 진행합니다.
while( n<=1 )
{
// 진행 방향에 따라 배열이 채워진다.
for(int i= 0; i<step; ++i)
{
// 1. 진행 방향에 따라, row, column을 지정
switch(direction)
{
case Direction::Down : ++row_index; break;
case Direction::Right : ++column_index; break;
case Direction::Up : --row_index; break;
case Direction::Left : --column_index; break;
}
// 해당하는 배열의 위치에 숫자를 채워넣는다.
arr[row_index][column_index] = num--;
}
// 2. 이동이 끝나면, 문제에서 주어진 순서대로 방향이 변경한다.
switch (dir)
{
// 이동해야하는 칸 수를 변경한다.
case Direction::Down: dir = Direction::Right;
--step;
break;
case Direction::Right: dir = Direction::Up;
break;
// 이동해야하는 칸 수를 변경한다.
case Direction::Up: dir = Direction::Left;
--step;
break;
case Direction::Left: dir = Direction::Down;
break;
}
}
이 문제에서는 Down->Right로, Up->Right로 방향이 변경될 때 이동해야 하는 칸의 수가 하나씩 줄어들었습니다.
이렇게 기본 틀을 유지한채로 문제를 응용해서 풀면 달팽이 배열 문제들을 풀 수 있습니다.
프로그래머스의 삼각 달팽이 문제를 살펴보면,
피라미드 모양의 달팽이 배열을 구현해야하는데요, 저는 아래 이미지와 같이 2차원 배열로 생각하여 구현하였습니다.
이때 배열에서 진행 방향의 이동 순서는 아래, 오른쪽, 대각선 위로 구현하여 풀었습니다.
의사 코드로 구현하면 아래와 같습니다.
for (int i = 0; i < index; ++i)
{
switch (dir)
{
case Direction::Down:
++row_index;
break;
case Direction::Right:
++column_index;
break;
// 대각선 위로 이동
case Direction::Up:
--row_index;
--column_index;
break;
}
arr[row_index][column_index] = num++;
}대각선 위로 이동해야하기 때문에, row와 column 인덱스를 전부 감소해 줍니다.
