[백준 3190] 뱀 (C++)

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

3190번: 뱀

옛날에 풀었던 문제이다.

뱀의 상태만 잘 처리하면 쉬운문제이다.

풀이는 다음과 같다.

snake의 좌표는 queue로 관리한다.

사실 queue로 뱀의 좌표를 관리하면 쉬운문제이다.

코드는 다음과 같다.

 

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#define MAX 100+1
using namespace std;
int N,K,L;
int map[MAX][MAX];
vector<pair<int, char>> vec;
queue<pair<int, int>> snake;
// 오른쪽 아래 왼쪽 위
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
void find() {
    int state = 0;
    int x = 1;
    int y = 1;
    map[x][y] = 1;
    int time = 0;
    int index = 0;
    snake.push(make_pair(x, y));
    while (1) {
        if (!vec.empty() && time == vec[index].first) {
            if (vec[index].second == 'L') {
                state = state - 1;
                if (state == -1) {
                    state = 3;
                }
            }
            if (vec[index].second == 'D') {
                state = state + 1;
                if (state == 4) {
                    state = 0;
                }
            }
            vec.erase(vec.begin());
        }
        time++;
        int next_x = x + dx[state];
        int next_y = y + dy[state];
        if (next_x >= 1 && next_x <= N && next_y >= 1 && next_y <= N) {
            if (map[next_x][next_y] == 0) {
                map[next_x][next_y] = 1;
                map[snake.front().first][snake.front().second] = 0;
                snake.pop();
                snake.push(make_pair(next_x, next_y));
                x = next_x;
                y = next_y;
            }
            else if (map[next_x][next_y] == 1)
                break;
            else if (map[next_x][next_y] == 2) {
                snake.push(make_pair(next_x, next_y));
                map[next_x][next_y] = 1;
                x = next_x;
                y = next_y;
            }
        }
        else
            break;
    }
    cout << time << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    cin >> K;
    for (int i = 0; i < K; i++) {
        int x, y;
        cin >> x >> y;
        map[x][y] = 2;
    }
    cin >> L;
    for (int i = 0; i < L; i++) {
        int x;
        char y;
        cin >> x >> y;
        vec.push_back(make_pair(x, y));
    }
    find();
}