[BOJ] 3190번 뱀 c++

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

문제
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

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

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

---

입력 1
6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

출력 1
9

---

입력 2
10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

출력 2
21

---

입력 3
10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

출력 3
13

---

#include <iostream>
#include <cstdio>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

int N, K;
int L;
int map[100][100] = {false,};
queue<pair<int, char> > rotation;
queue<pair<int, int> > q;
int sec = 0;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int dir = 3;

void move() {
  queue<pair<int, int> > tmp;
  pair<int, int> cur;
  pair<int, char> r;
  int hx, hy; // head
  int nx, ny;
  bool flag;

  hx = 0;
  hy = 0;
  q.push(make_pair(0, 0));

  while(!q.empty()) {
    sec += 1;

    cur = q.front();
    nx = hx + dx[dir];
    ny = hy + dy[dir];

    // if it touches a wall
    if(!(-1 < nx && nx < N && -1 < ny && ny < N))
      break;
    // if it touches its own body
    tmp = q;
    flag = false;
    while(!tmp.empty()) {
      if(tmp.front().first == nx && tmp.front().second == ny) {
        flag = true;
        break;
      }
      tmp.pop();
    }
    if(flag)
      break;

    hx = nx;
    hy = ny;
    q.push(make_pair(nx, ny));

    // if it is an apple
    if(map[nx][ny])
      map[nx][ny] = 0;
    else
      q.pop();

    if(!rotation.empty() && rotation.front().first == sec) {
      r = rotation.front();
      rotation.pop();
      if(r.second == 'L') {
        switch(dir) {
          case 0: dir = 2; break;
          case 1: dir = 3; break;
          case 2: dir = 1; break;
          case 3: dir = 0; break;
        }
      }
      else if(r.second == 'D') {
        switch(dir) {
          case 0: dir = 3; break;
          case 1: dir = 2; break;
          case 2: dir = 0; break;
          case 3: dir = 1; break;
        }
      }
    }
  }
}

int main() {
  int tmp1, tmp2;
  char ch;

  scanf("%d", &N);
  scanf("%d", &K);
  for(int i = 0; i < K; i++) {
    scanf("%d %d", &tmp1, &tmp2);
    map[tmp1 - 1][tmp2 - 1] = 1; // apple
  }

  scanf("%d", &L);
  for(int i = 0; i < L; i++) {
    scanf("%d %c", &tmp1, &ch);
    rotation.push(make_pair(tmp1, ch));
  }

  move();
  printf("%d\n", sec);
}

뱀의 몸이 위치한 좌표들을 어떻게 저장하느냐 했을 때 큐를 떠올리면 쉽게 풀 수 있을 것 같다.