백준) 3190 뱀

뱀

뱀 게임을 하는데 사과의 위치와 뱀의 이동방법까지 주어진다. 언제 게임오버 되는지 구해보자.

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

뱀이 머리, 꼬리 이동과 몸에 박아버리는 경우를 어떻게 관리할지 아이디어만 있으면 후다닥 풀린다.

뱀처럼 덱을 만들어서(이중 연결 리스트) 머리에 머리좌표를 넣고, 꼬리에 꼬리좌표를 넣으면 상수시간에 이동이 구현된다.

사과를 먹고, 몸에 박는 경우는 평소처럼 맵에 표시만 하면 된다.

방향이 현재 방향 기준으로 왼쪽 오른쪽으로 주어지는 터라, 현재 방향을 저장하면서,

모듈러 연산을 통해 나침반 돌아가는 것마냥 관리해주면 편하다.

대부분의 뱅뱅 도는 문제들에선 통용되는 아이디어다.

문제가 조금 불친절한데, x초에 c로 방향전환하라는 얘기는 이동 다하고 다음 이동에 c가 영향을 준다는 얘기다.

x가 같은 입력이 여러번 주어질수 도 있어서 방향 전환 정보를 한 번 보고 말게 아니다.

#include <stdio.h>
#include <deque>
#include <vector>
using namespace std;
 
typedef pair<int, int> pp;
deque<pp> bam;
vector<pp> cd;
pp cur;
 
int n, k, l, a, b, x, curd;
char c;
int map[100][100];
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
 
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < k; ++i) {
        scanf("%d %d", &a, &b);
        map[a - 1][b - 1] = 1;
    }
    scanf("%d", &l);
 
    for (int i = 0; i < l; ++i) {
        scanf("%d %c", &a, &c);
        if (c == 'L')
            b = 3;
        else
            b = 1;
        cd.push_back({ a,b });
    }
 
    int cdi = 0, t = 0;
    bam.push_front({ 0,0 });
    map[0][0] = 2;
 
    while(1) {
        t++;
        int xx = cur.first + dir[curd][0];
        int yy = cur.second + dir[curd][1];
 
        if (xx < 0 || xx >= n || yy < 0 || yy >= n)
            break;
        if (map[xx][yy] == 2)
            break;
 
        bam.push_front({ xx,yy });
        cur = { xx,yy };
        if (map[xx][yy] != 1) {
            map[bam.back().first][bam.back().second] = 0;
            bam.pop_back();
        }
        map[xx][yy] = 2;
 
        while (cdi < cd.size() && t == cd[cdi].first)
            curd = (curd + cd[cdi++].second) % 4;
    }
    
    printf("%d", t);
 
    return 0;
}