백준 3190번 - 뱀

백준 3190번 - 뱀

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

3190번: 뱀

이 문제는 시뮬레이션 문제이다. 

조건은 다음과 같다.

 

1.  뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
2.  만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
3.  만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉 몸길이는 변하지 않는다.

이 문제의 핵심은 뱀의 꼬리에 있다. 

뱀의 머리가 이동하는 것은 입력 받은데로 움직이면 되는데 뱀의 꼬리는 사과의 유무에 따라 달라진다.

즉 계속해서 뱀의 꼬리에 대한 정보를 가지고 있어야 한다.

queue를 사용하여 뱀이 움직일 때마다 queue에 push하고 만약 사과가 있다면 continue, 없다면 pop을 해준다.

뱀의 머리 이동은 pair를 사용해 구현하였다.

즉 이동하고 있던 방향에 따라 왼쪽으로 90도, 오른쪽으로 90도가 모두 달라지므로 미리 배열에 저장해 놓은 뒤

사용하였다.

코드는 다음과 같다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;
 
int main() {
    int n, k, l;
    int map[101][101];
    memset(map, 0, sizeof(map));
    scanf("%d", &n);
    scanf("%d", &k);
    int col, row;
    for (int i = 0; i < k; i++) {
        scanf("%d %d", &row, &col);
        map[row][col] = 1;
    }
    scanf("%d", &l);
    int x;
    char c;
    queue<pair<int, char>>change;
    for (int i = 0; i < l; i++) {
        scanf("%d %c", &x, &c);
        change.push(make_pair(x, c));
    }
    x = 1;
    int y = 1;
    int time = 0;
    map[x][y] = 2;
    int flag = 0;
    int pre_flag = 0;
    queue<pair<int, int>>snake;
    snake.push(make_pair(1, 1));
    pair<int, int>go[4] = { make_pair(0,1),make_pair(0,-1),make_pair(-1,0),make_pair(1,0) };
    int L[4] = { 2,3,1,0 };
    int D[4] = { 3,2,0,1 };
    while (1) {
        //nx, ny를 구현(다음에 갈 장소를 찾아야함)
        if (!change.empty() && time == change.front().first) {
            if (change.front().second == 'L')flag = L[pre_flag];
            else flag = D[pre_flag];
            change.pop();
        }
        int nx = x + go[flag].first;
        int ny = y + go[flag].second;
        if ((nx<1 || nx>n) || (ny<1 || ny>n) || map[nx][ny] == 2) { //종료 조건 두가지. 1.벽에 부딪혔을 때(범위 벗어났을 때), 2. 자기 자신과 부딪혔을 때
            printf("%d\n", time + 1);
            break;
        }
        if (map[nx][ny] == 0) {
            int sx = snake.front().first;
            int sy = snake.front().second;
            map[sx][sy] = 0;
            snake.pop();
        }
        map[nx][ny] = 2; //뱀이 있는 곳은 2로 표현
        snake.push(make_pair(nx, ny));
        x = nx;
        y = ny;
        pre_flag = flag;
        time++;
    }
}

뱀의 꼬리를 기억하는 큐나 덱을 잘 사용하면 문제를 해결 할 수 있다.