[BOJ] 3190. 뱀

[문제]

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

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

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.

• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.

• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

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

 

[풀이]

 

1) 단순하게 큐의 size = 뱀의 몸 길이 

1-1) map[][] = 0 ( 빈칸) 1 (뱀) 2 (사과)

 

2) 나아가는 방향이 빈칸(0) 이면 큐의 첫 번째 원소 (꼬리)를 큐에서 제거하고 (pop) 그 자리를 0으로 만들어준다. 

 

3) 나아가는 방향이 벽이거나 뱀(1) 이면 반복문을 중지하고 게임이 끝난다. 

 

4) 그 외이면 큐에 해당 좌표를 넣어준다. 그리고 그 자리를 뱀(1)로 만들어준다. (뱀의 몸길이 + 1)

 

5) x시간 후에는 방향을 전환한다. 

         L D

    상 좌 우

    하 우 좌

    좌 하 상

    우 상 하

 

직접 그림을 그려서 생각해보니 이런 결과가 나왔다. 이대로 방향을 리턴하는 함수를 작성하면 된다. 

#include <iostream> #include <vector> #include <queue> using namespace std; int n, k, l; int map[101][101]; typedef pair<int, char> ic; typedef pair<int, int> pp; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (int i = 0; i < k; i++) { int x, y; cin >> x >> y; map[x - 1][y - 1] = 2; //사과 } cin >> l; vector<ic> rot; for (int i = 0; i < l; i++) { int x; char c; cin >> x >> c; rot.push_back(ic(x, c)); } int seq = 0, idx = 0; queue<pp> q; q.push(pp(0,0)); int dir = 3; int x = 0, y = 0; map[x][y] = 1; //북 남 서 동 while (1) { seq++; int nx = x + dx[dir]; int ny = y + dy[dir]; if (nx < 0 || nx >= n || ny < 0 || ny >= n || map[nx][ny] == 1) break; if (seq == rot[idx].first) { if (rot[idx].second == 'L') { dir = dir < 2 ? dir + 2 : 3 - dir; } else { dir = dir < 2 ? 3 - dir : dir - 2; } idx++; } if (!map[nx][ny]){ //빈칸이라면 if (!q.empty()) { pp tail = q.front(); q.pop(); map[tail.first][tail.second] = 0; } } q.push(pp(nx, ny)); map[nx][ny] = 1; x = nx; y = ny; } cout << seq << '\n'; return 0; }