3190 - c++

---

요약

우리가 아는 뱀 게임과 똑같다 사과를 먹으면 몸의 길이가 늘어나고 그게 아니라면 이동하는 방식

 

---

아이디어

방향을 저장할 변수가 필요하다 (dir)

동서남북을 숫자로 지정해 준다 (동 = 0, 남 = 1, 서 = 2, 북 = 3)

 

문제 몸이 꺾였을 때 뱀의 꼬리는 흔들림 없이 편안하게 꺾여야 함 즉 머리만 꺾여야 함

꺾일 때 머리만 꺾여야한다

이 부분을 고민하면서 자료구조 큐를 써야 함을 알게 되었다.

굳이 복잡하게 머리를 꺾으면 꼬리를 가만히 있어야 되고... 이러쿵저러쿵하기보다 간단하게!

큐를 써서 추가될 때마다 큐에 집어넣어 준다면  꼬리는 당연하게도 큐의 가장 앞에 위치하게 될 것이다. 맞쥬?

 

1. 내가 가게 될 다음칸에 사과가 있으면 다음 위치를 큐에 추가해 주고

2. 만약 빈칸이라면 큐에서 꼬리를 pop() 해주고 다음 위치를 큐에 push 해주면 된다!

 

자 이제 명령에 따른 방향이동이 남았다

아까 방향(동 = 0, 남 = 1, 서 = 2, 북 = 3) 설정을 위와 같이 한 이유는 편하게 하기 위해서다

1. 시계 방향

(dir + 1) % 4

2. 반시계 방향

(dir + 3) % 4

이렇게 하면 계산이 편해진다!

 

방향에 따른 이동은 dx, dy로 나타낸다

//동 = 0, 남 = 1, 서 = 2, 북 = 3
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

자 그럼 코드로 구현해 보자

 

---

CODE

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int board[101][101];
int n, k, dir = 0, times = 0; //처음 방향은 무조건 동쪽을 향함
int x = 1, y = 1;

queue<pair<int, char>> commands;
queue<pair<int, int>> tails;

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

int cmdTime;
char cmdDir;

bool OOB(int nx, int ny){
  return nx < 1 || nx > n || ny < 1 || ny > n || board[nx][ny] == 1;
}

int main()
{
  init();
  cin >> n >> k;
  board[x][y] = 1; //가장 북쪽의 가장 서쪽은 무조건 뱀이 있음
  tails.push({x, y});

  while(k--){
    int x, y;
    cin >> x >> y;
    board[x][y] = 2;
  }

  cin >> k;
  while(k--){
    int times;
    char dirs;
    cin >> times >> dirs;
    commands.push({times, dirs});
  }
  
  bool isCompleted = true;
  while(1){
    if(!commands.empty() && isCompleted){
      auto cur = commands.front();commands.pop();
      cmdTime = cur.first;
      cmdDir = cur.second;
      isCompleted =false;
    }
    if(cmdTime == times){
      dir = (cmdDir == 'D') ? (dir+1)%4 : (dir+3)%4;
      isCompleted = true;
    }
    ++times;

    x += dx[dir];
    y += dy[dir];

    if(OOB(x, y)){//게임끝인지 확인
      cout << times<<'\n';
    }

    if(board[x][y] == 0){//그저 빈칸이라면 꼬리 자르고 앞에 머리 추가
      pair<int, int> t = tails.front(); tails.pop();
      board[t.first][t.second] = 0;
    }
    board[x][y] = 1;
    tails.push({x, y});
  }
  return 0;
}

 

비효율 적인 부분을 설명하자면

if(!commands.empty() && isCompleted){
      auto cur = commands.front();commands.pop();
      cmdTime = cur.first;
      cmdDir = cur.second;
      isCompleted =false;
    }
    if(cmdTime == times){
      dir = (cmdDir == 'D') ? (dir+1)%4 : (dir+3)%4;
      isCompleted = true;
    }

isComplete라는 변수를 따로 만들었다. 이 변수는 명령어가 처리되었는지를 알려주는 변수이다.

명령 큐에서 가져온 명령이 처리되어야지만 명령 큐에서 다른 명령어를 가져올 수 있기 때문이다.

 

내가 구상한 코드에서 isComplete가 없었다면 계속 입력받은 명령을 수행했는지 성공했는지는 궁금해하지 않고 그저 매초 뱀이 이동할 때마다 명령 큐에서 명령어를 가져오는 일이 발생한다....

 

---

시행착오

예제 1번 입력에서 계에에에에에에속 오류가 났다 대체 왜?? 왜???

알고 보니 처음 시작하는 장소를 꼬리 큐에 안 넣어 줘서 segmentation fault가 생겼던 것이다.

찾고 나니 행복했다.