[C++] 백준 - 3190 : 뱀

문제 링크

3190번: 뱀

 

풀이 )

  개인적인 편의상 이차원배열에서 좌표를 [y][x]로 했다.

 

  먼저 뱀의 몸이 지나고 있는 자리 board를 배열로 나타내고, 사과 apple의 위치를 나타내기 위한 배열을 따로 만들었다.

  그리고 뱀의 몸을 나타내기 위한 큐 snake와 방향 회전 turn을 만들었다.

  

  먼저 현재 좌표(curY, curX)가 보드 안에 있는지(벽에 부딪힌지 여부) 확인한 후, 몸에 부딪혔는지 확인하여 부딪혔다면 반복문을 종료하고 결과를 출력한다.

 

  현재 좌표에 뱀의 머리가 있으므로 뱀에 넣어주고 board의 현재 위치를 1로 만들어준다. 그리고 현재 위치에 사과가 없다면(!apple[curY][curX]) 뱀의 꼬리, 즉 가장 먼저 들어간 원소이므로 front()에 있는 board를 0으로 만들어준다.

  사과가 있다면 사과를 먹었으므로 다시 apple[curY][curX]를 0으로 만들어준다.

 

  다음 회전을 기다리기 위해 회전할 초를 저장하는 next를 만들었다.

  next가 비어있는 경우 turn 큐에서 pop을 해서 몇초인지 next에 넣어주고, 어떤 방향인지 next_dir에 넣어준다.

  이후 회전하는 시간이 되면(ans == next) 방향에 맞게 회전해준다.

  dx, dy를 각각 시계방향으로 만들었기 때문에 오른쪽이면 (dir+1)%4, 왼쪽이면 (dir-1+4)%4로 해준다. 이 때 왼쪽의 경우 +4를 해주어 dir이 음이 되는 것을 방지한다.

 

  이후 현재의 좌표를 이동시키고 다음 반복문을 진행한다.

 

#include <cstdio>
#include <queue>	// queue
#include <utility>	// pair
using namespace std;

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

int main(void)
{
  int n, k, l, board[101][101] = {0, }, apple[101][101] = {0, };
  char c[101] = "";
  queue<pair<int, int>> snake;
  queue<pair<int, char>> turn;

  scanf("%d%d", &n, &k);
  for(int i = 0; i < k; ++i){
    int x, y;
    scanf("%d%d", &y, &x);
    apple[y][x]++;
  }
  scanf("%d", &l);
  for(int i = 0; i < l; ++i){
    int x;
    char dir;
    scanf("%d %c", &x, &dir);
    turn.push(make_pair(x, dir));
  }

  int ans = 0, curX = 1, curY = 1, dir = 1, next = 0;
  char next_dir;

  while(1){
    // 부딪힌지 여부
    if(curX < 1 || curX > n || curY < 1 || curY > n)
      break;
    if(board[curY][curX])
      break;

    snake.push(make_pair(curY, curX));
    board[curY][curX] = 1;
    // 사과가 없을 때
    if(!apple[curY][curX] && ans){
      int tmpX, tmpY;
      tmpX = snake.front().second;
      tmpY = snake.front().first;
      snake.pop();
      board[tmpY][tmpX] = 0;
    }
    // 사과가 있을 때
    else
      apple[curY][curX] = 0;

    // 다음 회전
    if(next == 0){
      next = turn.front().first;
      next_dir = turn.front().second;
      turn.pop();
    }
    if(ans == next){
      next = 0;
      if(next_dir == 'L')
        dir = (dir+3)%4;
      else
        dir = (dir+1)%4;
    }
    ans++;
    curX += dx[dir];
    curY += dy[dir];
  }
  printf("%d\n", ans);
  return 0;
}

 

주의점 )

  - 좌표 범위

  - 회전