[BOJ] 뱀_3190번 C++ 풀이

문제

NxN 정사각 보드위에서 길이가 1인 뱀이 맨위 맨 좌측에서 부터 오른쪽으로 이동하고 사과를 먹으면 길이가 늘어난다. ‘게임 시작 시간’ 으로 부터 t초가 지난 시간 뒤에 방향 전환을 하는것인데 문제를 잘못 이해하여 고생한 문제이다. 항상 문제를 접근하기 전에 문제를 정확히 이해하고 재정의 해봐야 하는데 문제를 대충 읽고 그림을 보고 문제를 유추하는 실수를 범했다.

접근 방법

NxN 정사각 보드를 2차원 배열 matrix로 나타내었고 보드에 사과가 존재하는 위치를 1, 뱀의 몸이 존재하는 위치를 2로 하여 삽입하였다.
큐를 사용하여 뱀의 위치를 저장하였으며 뱀의 머리가 이동할때 마다 이동한 머리의 위치를 snake큐에 삽입하였고 사과를 먹었는지의 여부에 따라 꼬리 부분에 해당하는 snake큐의 front를 pop하거나 안하는 경우로 나누었다.

t초후의 뱀의 방향전환은 행과 열을 포함한 ‘dir’ 구조체를 선언하여 방향 전환이 ‘D’, ‘L’인 경우를 나누어 동서남북 4가지 경우 중 알맞은 방향으로 전환할 수 있도록 하였다.

if(turn.front().second=='D') curIdx=(curIdx+1)%4;
else curIdx=(curIdx+3)%4;

구현

#include<iostream>
#include<queue>
using namespace std;

typedef struct
{
    int r,c;
} dir;

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int matrix[101][101]; // 1=사과 위치, 2=뱀의 몸통 위치
    int n, k, row, col, l, t;
    char c;
    int sum=0;
    int curIdx=0;
    int time=0;
    int prev=0;
    pair<int, int> curPos = (make_pair(0,0)); //현재 뱀의 머리 위치 나타내는 변수
    dir d[4]={ {0,1}, {1,0}, {0,-1}, {-1,0} }; //동남서북
    queue<pair<int, char> > turn;
    queue<pair<int, int> > snake;
    snake.push(make_pair(0,0));
    
    cin>>n;
    cin>>k;
    for(int i=0; i<k; i++)
    {
        cin>>row>>col;
        matrix[row-1][col-1]=1;
    }

    cin>>l;
    for(int i=0; i<l; i++)
    {
        cin>>t>>c;
        turn.push(make_pair(t,c));
    }

    while(1)
    {
        if(!turn.empty())
        {
            time=turn.front().first-prev;
            prev=turn.front().first;
        }
        else
        {
            time=100000;
        }

        for(int i=0; i<time; i++)
        {
            sum++;
            curPos.first+=d[curIdx].r;
            curPos.second+=d[curIdx].c;

            if(curPos.first>=n || curPos.second>=n) // 벽에 부딫힌 경우
            {
                cout<<sum;
                return 0;
            }

            if( curPos.first<0 || curPos.second<0) // 벽에 부딫힌 경우
            {
                cout<<sum;
                return 0;
            }

            if(matrix[curPos.first][curPos.second]==2) // 뱀이 자기 몸통에 부딫히는 경우
            {
                cout<<sum;
                return 0;
            }

            if(matrix[curPos.first][curPos.second]==1) // 뱀의 머리가 이동한 위치에 사과 있을 경우
            {
                matrix[curPos.first][curPos.second]=2; //뱀의 위치 표시
                snake.push(make_pair(curPos.first, curPos.second));
            }
            else
            {
                matrix[curPos.first][curPos.second]=2; //뱀의 위치 표시
                snake.push(make_pair(curPos.first, curPos.second));
                matrix[snake.front().first][snake.front().second]=0; //꼬리 부분 이동 
                snake.pop();
            }
        }
        if(turn.front().second=='D') curIdx=(curIdx+1)%4;
        else curIdx=(curIdx+3)%4;

        turn.pop();
    }
    return 0;
}

BOJ_뱀_3190