백준 3190 뱀

1. 문제를 꼼꼼히 읽습니다. 2. 사용하는 변수와 자료구조를 고려하여 선택합니다.

/*
3190 뱀

19:45 시작합니다.
20:24

39분컷

설계 과정
1. 문제를 꼼꼼하게 읽습니다.
2. 설계를 완벽하게 합니다. (예제 3개 돌리기)
3. 경우의 수를 나열합니다.
4. 초기화 변수를 확인합니다.
5. 가지치기를 합니다.
6. 예제와 동일한 변수를 선언하고 사용합니다.

풀이 과정
1. 뱀에 해당하는 벡터를 사용합니다.
2. 명령어에 따라 행동하도록 합니다.

- 맵 안에서 움직이므로, 인덱스를 주의합니다.
*/
 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
#define SIZE 105 // 105
int N, K, L;
struct point {
    int sec;
    char cha;
};
int ans;
int a, b;
int map[SIZE][SIZE];
int index;
struct point2 {
    int x, y;
};
queue<point2> que;
queue<point> command;
int x, y, nx, ny, dir;
int dx[] = { 0,1,0,-1 }; // 동 남 서 북
int dy[] = { 1,0,-1,0 };
int sec;
int c;
char d;
 
void problemIn() {
    cin >> N;
    cin >> K;
    for (int i = 0; i < K; i++) {
        cin >> a >> b;
        map[a][b] = 2; // 사과 입력
    }
    cin >> L;
    for (int i = 0; i < L; i++) {
        cin >> c >> d;
        command.push({ c,d });
    }
}
 
void init() {
 
}
 
void solve() {
 
    x = 1;
    y = 1;
    dir = 0;
    que.push({ x,y });
    map[x][y] = 1; // 뱀을 1로 표시
 
    while (1) {
 
        sec++;
 
        nx = x + dx[dir];
        ny = y + dy[dir];
        x = nx;
        y = ny;
 
        // 몸이나 벽에 부딪히면,
        if (nx < 1 || ny < 1 || nx > N || ny > N || map[nx][ny] == 1) {
            ans = sec;
            return;
        }
        // 사과를 먹으면
        else if (map[nx][ny] == 2) {
            map[nx][ny] = 1;
            que.push({ nx,ny });
        }
        else {
            // 사과, 몸, 벽이 아니면 뱀을 이동시키기.
            map[nx][ny] = 1;
            que.push({ nx,ny });
            map[que.front().x][que.front().y] = 0;
            que.pop();
        }
 
        if (!command.empty()) {
            if (command.front().sec == sec) {
                if (command.front().cha == 'D') {
                    dir = (dir + 1) % 4;
                }
                else {
                    dir = (dir - 1 + 4) % 4;
                }
                command.pop();
            }
        }
    }
}
 
int main() {
    problemIn();
    solve();
    cout << ans << endl;
    return 0;
}