[3190] 뱀

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

오늘 문제는 뱀이다.

뱀이 이동하는 것을 시뮬레이션 할 수 있냐고 물어보는 문제이다.

문제의 조건은 다음 두 가지이다.

1. 뱀은 사과를 먹으면 몸 길이가 1 늘어난다.

2. 이동 중 자신의 몸이나 벽에 부딪히면 그때까지의 시간을 출력하면 된다.

3. 사과가 없으면 꼬리쪽이 줄어들어 몸 길이가 유지된다.

문제를 푸는 아이디어는 무척 쉽다. 그냥 구현하면 된다.

만약 코드 작성이 잘 안된다면 아래의 보기 중 문제가 있을 것 같다.

1. 방향 전환

2. 문제이해

3. 꼬리

먼저 이런 문제를 많이 안 풀어 봤으면 방향 전환을 어떻게 해야하나 어렵게 느껴질 수 있다

나는 배열을 이용해 방향 전환을 했다.

            //상 우 하 좌
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
        
 
if(vt[cnt] == 'D'){
    d = (d+1)%4;
}
else if(vt[cnt] == 'L'){
     d = (d+3)%4;
}

위와 같이 dx, dy  배열을 시계 방향대로 상 우 하 좌 순서대로 만들어 놓는다.

그 후 방향 전환을 해야할 때 시계 방향은 +1, 반시계 방향은 +3을 해주면 된다.

헷갈리면 손으로 그려가면서 해보길 추천한다.

다음은 X초 후 방향 전환에서 X초 때문에 문제를 잘못 풀수도 있다.

문제에서 나온 3 D, 15 D의 의미는

3초 동안 현재 방향으로 진행한 후 D로 방향 전환하고

그 다음 15초가 아닌 12초 동안 현재 방향으로 진행한 후 D로 방향 전환의 의미이다.

즉 X초는 처음 시작 시간으로부터 흐른 시간이다.

그 다음으로 꼬리가 문제가 된다.

꼬리를 원활히 줄어들게 하기 위해선 방향의 기록이 필요하다.

즉, 현재 머리가 향하는 방향을 꼬리에게 그대로 적용하면 꼬리는 오른 쪽을 보고 있어야 하는데

머리가 아래 쪽으로 방향 전환을 했다고 꼬리도 아래 쪽으로 움직이면 안된다는 것이다.

처음에 이렇게 코드를 작성했다가 꼬리가 줄어들지 않아 디버깅 해보고 고쳤다.

끝.

#include<cstdio>
#include<algorithm>
using namespace std;
int arr[110][110], direct[110][110];
char vt[10100];
            //상 우 하 좌
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
 
int main(){
    int n, k, l, x, y, z, cnt, d;
    char c;
    scanf("%d %d", &n, &k);
    for(int i=0; i<k; i++){
        scanf("%d %d", &x, &y);
        arr[x][y] = 2;
    }
    scanf("%d", &l);
    for(int i=0; i<l; i++){
        scanf("%d %c", &z, &c);
        vt[z] = c;
    }
 
    arr[1][1] = 1;
    cnt = 0, d = 1;
    direct[1][1] = d;
    int tx, ty, hx, hy;
    tx = hx = ty = hy = 1;
    while(1){
        if(vt[cnt] == 'D'){
            d = (d+1)%4;
        }
        else if(vt[cnt] == 'L'){
            d = (d+3)%4;
        }
        if(hx+dx[d]<=0 || hx+dx[d]>n || hy+dy[d]<=0 || hy+dy[d]>n){
            break;
        }
        if(arr[hx + dx[d]][hy + dy[d]] == 1){
            break;
        }
        direct[hx][hy] = d;
        hx += dx[d];
        hy += dy[d];
        if(arr[hx][hy] != 2){
            arr[tx][ty] = 0;
            int ttx = tx;
            int tty = ty;
            tx += dx[direct[ttx][tty]];
            ty += dy[direct[ttx][tty]];
        }
        arr[hx][hy] = 1;
        cnt++;
    }
    printf("%d\n", cnt+1);
 
    return 0;
}