[ 백준 3190 ] 뱀 (C++)

백준의 뱀(3190) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 대표적인 시뮬레이션 문제이다. 먼저, 뱀이 어떻게 움직이는지 조건부터 다시 한번 확인해보자.

   위의 사진은 뱀이 움직일 때의 규칙 혹은 조건이다. 위에 조건에는 안나와있지만, 뱀은 입력으로 주어지는 특정시간마다

   특정 방향으로 회전을 하게 된다.

2. 먼저 나는 이 문제를 보고 디큐(DeQueue)를 생각했다.

   2-1) DeQueue???

   - 우리가 많이 사용하는 큐(Queue)는 선입선출 구조이다. 즉, push를 할 때에는 제일 뒤쪽으로 밖에 push할 수 없고

     pop을 할 때에는 가장 앞쪽에서 밖에 pop을 하지 못하는게 Queue이다.

     반면에 Dequeue는 앞/뒤쪽에 push가 모두 가능하고, pop 또한 앞/뒤쪽에서 pop이 가능하다. 많이 사용되는 자료구조는

     아니지만, 한번씩 사용하기 좋은 점이 있다.

   - 이 문제 같은 경우 뱀의 머리가 움직이면서, 꼬리가 따라오는 경우가 있고, 그렇지 않은 경우가 있다.

     좀 더 구체적으로 말하자면 사과를 먹게되면 꼬리와 몸통은 그대로 있고, 뱀의 머리만 한 칸 더 나아가게 된다.

     반면에 사과가 없는 곳이라면, 뱀의 머리가 나아감과 동시에, 꼬리는 사라지게 된다.

     뱀의 머리와 꼬리를 관리하는 것과, Dequeue의 특성을 잘 생각해보면 Dequeue가 꽤 괜찮다고 생각될 것이다.

   이제부터 조건을 하나하나 따져가면서 뱀을 움직여보자.

   나는 MAP에서 사과가 있는 부분을 1로, 뱀이 있는 곳을 2로 표시하면서 진행하였다.

   가장 먼저 (0, 0)에서 시작하므로, (0, 0)을 Dequeue에 넣어주고, MAP[0][0] = 2로 표시해두고 시작하였다.

  

   뱀을 진행시킬 때 조건에만 조건문을 구현만 해주면 된다.

   먼저 나는 뱀의 진행방향대로 현재 뱀의 머리좌표를 진행방향으로 +1칸 되도록 좌표를 움직여주었다.

   이제 뱀의 움직이에 영향을 주는 조건들에 대해서 설명하겠다.

   1. 움직인 좌표가 맵의 범위를 넘어가거나, 아니면 뱀의 몸뚱아리가 있는 곳이라면 ?

   2. 움직인 좌표가 맵에서 아무것도 없는 빈공간이라면?

   3. 움직인 좌표가 맵에서 사과가 있는 공간이라면?

   4. 현재 시간이 만약 뱀이 움직이는 방향을 바꾸는 시간이라면?

 

   1번 조건은 조건에도 나와있는 것 처럼, 그대로 프로그램을 종료하면 된다.

   2번 조건은 뱀의 머리가 한칸 더 나아가고, 꼬리는 사라지게 된다.

       즉, MAP[nx][ny] = 2 가 되고,(nx, ny = x, y에서 나아간 다음 칸)

       꼬리가 사라져야 하기 때문에, MAP[Q.back().first][Q.back().second] = 0이 되게 된다.

       여기서 Q는 앞에서 말한 DeQueue를 의미한다.

       그 후 Q.pop_back()을 통해 꼬리를 없애주고, Q.push_front(nx,ny)를 통해 새로운 뱀의 머리 좌표를 저장해준다.

   3번 조건은 꼬리는 가만히 있고, 뱀의 머리만 한칸 더 나아가면 된다.

       즉, MAP[nx][ny] = 2 가 되고, Q.push_front(nx,ny)를 통해 새로운 뱀의 머리 좌표를 저장해주기만 하면 된다.

   4번 조건은 현재 시간과, 입력으로 받은 시간을 비교해서 같다면, 뱀의 진행방향만 바꿔주면 된다.

   조건 몇가지만 잘 생각하면서 구현을 한다면 어렵지 않을 것이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<deque>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int N, K, L;
int MAP[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
vector<pair<int, char>> V;
 
void Print()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << MAP[i][j] << " ";
        }
        cout << endl;
    }
}
void Input()
{
    cin >> N >> K;
    for (int i = 0; i < K; i++)
    {
        int x, y;
        cin >> x >> y;
        x = x - 1;
        y = y - 1;
        MAP[x][y] = 1;    // 사과 = 1로 표시
    }
    cin >> L;
    for (int i = 0; i < L; i++)
    {
        int a; 
        char b;
        cin >> a >> b;
        V.push_back(make_pair(a, b));
    }
}
 
int Turn_Direction(int d, char c)
{
    if (c == 'L')
    {
        if (d == 0) return 3;
        else if (d == 1) return 2;
        else if (d == 2) return 0;
        else if (d == 3) return 1;
    }
    else if (c == 'D')
    {
        if (d == 0) return 2;
        else if (d == 1) return 3;
        else if (d == 2) return 1;
        else if (d == 3) return 0;
    }
}
 
void Solution()
{
    deque<pair<int, int>> Q;
    int x = 0;
    int y = 0;
    int d = 0;
    int Time = 0;
    int Idx = 0;
    Q.push_back(make_pair(x, y));
    MAP[x][y] = 2;
 
    while (1)
    {
        Time++;
 
        int nx = x + dx[d];
        int ny = y + dy[d];
        
        if ((nx < 0 || ny < 0 || nx >= N || ny >= N) || MAP[nx][ny] == 2)
        {
            break;
        }
        else if (MAP[nx][ny] == 0)
        {
            MAP[nx][ny] = 2;
            MAP[Q.back().first][Q.back().second] = 0;
            Q.pop_back();
            Q.push_front(make_pair(nx, ny));
        }
        else if (MAP[nx][ny] == 1)
        {
            MAP[nx][ny] = 2;
            Q.push_front(make_pair(nx, ny));
        }
        
 
        if (Idx < V.size())
        {
            if (Time == V[Idx].first)
            {
                if (V[Idx].second == 'L') d = Turn_Direction(d, 'L');
                else if (V[Idx].second == 'D') d = Turn_Direction(d, 'D');
                Idx++;
            }
        }
        x = nx;
        y = ny;
    }
    cout << Time << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}