4-14. 달팽이 문제

1. 기본 코드

#include <iostream>
#include <iomanip>

using namespace std;

const int MAX = 100;
int board[MAX][MAX] = {};
int N;

void PrintBoard()
{
    for (int y = 0; y < N; y++)
    {
        for (int x = 0; x < N; x++)
        {
            
            cout << setfill('0') << setw(2) << board[y][x] << " ";
        }
        cout << endl;
    }
}

enum DIR
{
    RIGHT = 0,
    DOWN,
    LEFT,
    UP
};

 

2. 벽 판단

더 진행할 수 있는지 판단한다.

bool CanGo(int y, int x)
{
    if (y < 0 || y >= N)
        return false;
    if (x < 0 || x >= N)
        return false;
    if (board[y][x] != 0)
        return false;
    return true;
}

N * N의 사각형 외부로 나가지 못하게 설정한다.

 

3. 메인 코드

void SetBoard()
{
    int dir = RIGHT;
    int x = 0;
    int y = 0;
    int num = 1;

    while(true)
    {
        board[y][x] = num;

        if (num == N * N)
            break;

        int nextY;
        int nextX;

        switch(dir)
        {
        case RIGHT:
            nextY = y;
            nextX = x + 1;
            break;

        case DOWN:
            nextY = y + 1;
            nextX = x;
            break;

        case LEFT:
            nextY = y;
            nextX = x - 1;
            break;

        case UP:
            nextY = y - 1;
            nextX = x;
            break;
        }

        if (CanGo(nextY, nextX))
        {
            y = nextY;
            x = nextX;
            num++;
        }
        else
        {
            switch(dir)
            {
                case RIGHT:
                dir = DOWN;
                break;
                case DOWN:
                dir = LEFT;
                break;
                case LEFT:
                dir = UP;
                break;
                case UP:
                dir = RIGHT;
                break;
            }
        }
    }

4. 코드 분석

(1) 진행방향 구성

board[y][x] = num;

        if (num == N * N)
            break;

        int nextY;
        int nextX;

        switch(dir)
        {
        case RIGHT:
            nextY = y;
            nextX = x + 1;
            break;

        case DOWN:
            nextY = y + 1;
            nextX = x;
            break;

        case LEFT:
            nextY = y;
            nextX = x - 1;
            break;

        case UP:
            nextY = y - 1;
            nextX = x;
            break;
        }

먼저 숫자가 최대 숫자인 N * N에 도달하면 반복문을 종료한다.

이후 다음 좌표를 판단하는 nextY, nextX를 선언한다.

다음 switch case 문을 이용하여 오른쪽으로 진행한다면 x좌표를 1 증가, 아래는 y좌표를 1 증가, 왼쪽은 x좌표를 1 감소, 위는 y 좌표를 1 감소하게 설정한다.

 

(2) 방향 전환

        if (CanGo(nextY, nextX))
        {
            y = nextY;
            x = nextX;
            num++;
        }
        else
        {
            switch(dir)
            {
                case RIGHT:
                dir = DOWN;
                break;
                case DOWN:
                dir = LEFT;
                break;
                case LEFT:
                dir = UP;
                break;
                case UP:
                dir = RIGHT;
                break;
            }
        }

이후 불리언으로 설정했던 CanGo를 이용하여 충돌여부를 확인한 후에, N * N의 벽에 충돌했다면 방향을 전환하는 코드를 만들어준다.

 

오른쪽 벽에 부딫혔다면 방향을 아래로

아래쪽 벽에 부딫혔다면 방향을 왼쪽으로

왼쪽 벽에 부딫혔다면 방향을 위로

위쪽 벽에 부딫혔다면 방향을 오른쪽으로 진행하게 된다.

 

5. 코드 최적화

(1) 진행 코드 최적화

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

    while(true)
    {
        board[y][x] = num;

        if (num == N * N)
            break;

        int nextY = y + dy[dir]
        int nextX = x + dx[dir]

switch case 문을 제거하고 위의 배열을 사용하면 코드를 줄일 수 있다.

 

(2) 방향 전환 코드 최적화

      dir = (dir + 1) % 4;

방향 전환 switch case 문을 제거하고 위처럼 하면 방향을 올바르게 설정할 수 있다.