백준 3190 - 뱀

문제

 

https://www.acmicpc.net/problem/3190

3190번: 뱀

 

 

풀이

 

문제에 나와있는 순서대로 구현을 해주면 된다. 특별히 신경 쓴 부분은 종료조건과 꼬리의 이동 부분이다. 

 

뱀의 몸이 있는 공간을 check 배열을 통해 나타냈다. check[x][y] = true 일 경우 x,y에는 뱀의 몸이 있는 것이다. 또한 뱀이 이동할 수 없는 벽도 check 배열을 통해 나타냈다. 따라서 check[x][y]=true 일 경우 x, y 좌표는 벽 또는 뱀의 몸을 의미한다. 뱀이 다음에 이동할 공간의 dx,dy 값에서 check[dx][dy] = true 일 경우 게임이 종료된다.

 

뱀이 이동할때 머리가 먼저 이동한 후 꼬리가 움직이는데, 꼬리에 해당하는 좌표 x,y 값을 이용해 check[x][y] = false로 해준다. 이때 현재 꼬리 좌표 값을 이동한 뱀의 꼬리 좌표 값으로 새로 갱신을 해줘야 한다. 이를 위해서 뱀의 머리가 이동할 때 다음에 이동할 좌표를 큐에 저장을 해준다. 그러면 큐에 저장된 좌표 값들은 뱀의 꼬리 좌표 값으로도 사용할 수 있게 된다. 큐에 있는 좌표를 이용해 뱀의 꼬리 값을 새로 갱신해준다.

 

코드

 

#include <iostream>
#include <queue>
 
using namespace std;
 
int N, K, L;
int graph[101][101];
bool check[102][102];
int cnt;
int dx = 1, dy = 1;
int d = 1;
pair<int, int> head[4] = {{-1,0},{0,1},{1,0},{0,-1}};
queue<pair<int, int>> tail;
queue<pair<int, char>> change;
 
int right(int d)
{
    return (d + 1 > 3) ? 0 : d + 1;
}
 
int left(int d)
{
    return (d - 1 < 0) ? 3 : d - 1;
}
 
void solve()
{
    while (true)
    {
        dx += head[d].first;
        dy += head[d].second;
 
        if (check[dx][dy]) break;
 
        check[dx][dy] = true;
        tail.push({ dx, dy });
        
        if (graph[dx][dy])
            graph[dx][dy] = 0;
        else
        {
            check[tail.front().first][tail.front().second] = false;
            tail.pop();
        }
 
        cnt++;
 
        if (cnt == change.front().first)
        {
            if (change.front().second == 'D') d = right(d);
            else d = left(d);
            change.pop();
        }
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N >> K;
    for (int i = 0; i < K; i++)
    {
        int x, y;
        cin >> x >> y;
        graph[x][y] = 1;
    }
    cin >> L;
    for (int i = 0; i < L; i++)
    {
        int a; char b;
        cin >> a >> b;
        change.push({a, b});
    }
    for (int i = 0; i <= N + 1; i++)
        check[i][0] = check[i][N+1] = check[0][i] = check[N + 1][i] = true;
    
    check[dx][dy] = true;
    tail.push({dx,dy});
 
    solve();
 
    cout << cnt + 1;
    return 0;
}