[3190] 뱀

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

3190번: 뱀

<문제>

뱀이 지나간 경로를 전부 저장해둔다면

ail의 위치는 뱀의 머리가 몇번째로 방문한 곳인지를 인덱스로 접근할 수 있다. 

입력으로 들어오는 방향전환은 시간을 기준으로 오름차순 정렬되어 있으니 현재 턴과 비교하여

왼쪽으로 90도, 오른쪽으로 90도씩 돌려주어야 한다. 항상 X초 이후에 처리해야 하는것에 유의해야한다.

뱀이 존재하는 위치는 bool check[][]에 표시해주었고, 이를 통해 뱀의 머리와, 뱀의 몸의 충돌을 파악했다.

그밖에 사과를 한번 방문하면 사과를 없애주어야 하는점도 주의해야한다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int a[101][101], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0}, n, k, l,
                 turn = 1, curY = 1, curX = 1, lastY = 1, lastX = 1, curDir,
                 tailIdx, Qidx;
bool check[101][101];
vector<pair<int, int>> path;
vector<pair<int, char>> query;
int main(void) {
    cin >> n >> k;
    int i, j;
    for (i = 0; i < k; i++) {
        int y, x;
        cin >> y >> x;
        a[y][x] = 1;
    }
    cin >> l;
    for (i = 0; i < l; i++) {
        int x;
        char c;
        cin >> x >> c;
        query.push_back({x, c});
    }
    check[1][1] = true;
    path.push_back({1, 1});
    while (1) {
        int nextY = curY + dy[curDir];
        int nextX = curX + dx[curDir];
        if (nextY < 1 || nextX < 1 || nextY > n || nextX > n ||
            check[nextY][nextX])
            break;
        path.push_back({nextY, nextX});
        check[nextY][nextX] = true;
        if (a[nextY][nextX] == 1) {
            a[nextY][nextX] = 0;
        } else {
            check[lastY][lastX] = false;
            tailIdx++;
            lastY = path[tailIdx].first;
            lastX = path[tailIdx].second;
        }
        curY = nextY;
        curX = nextX;
        if (Qidx < l && query[Qidx].first == turn) {
            char nDir = query[Qidx].second;
            if (nDir == 'L') {
                curDir--;
                if (curDir == -1) curDir = 3;
            } else if (nDir == 'D') {
                curDir++;
                if (curDir == 4) curDir = 0;
            }
            Qidx++;
        }
        turn++;
    }
    cout << turn;
    return 0;
}