문제
https://www.acmicpc.net/problem/3190
뱀의 초기 상태 (화살표의 머리를 뱀의 머리라고 생각하자.)
- 위치: (0, 0)
- 길이: 1
- 방향: 오른쪽
뱀의 이동 규칙
- 뱀은 현재 방향에 따라 매초에 한칸씩 전진한다.
- 몸 길이를 늘려 머리를 다음 칸에 위치시킨다.
- 벽이나 자기자신의 몸과 부딪히면 게임이 종료된다.
- 이동한 칸에 사과가 있다면, 그 사과를 먹고 꼬리는 움직이지 않는다.
- 이동한 칸에 사과가 없다면, 몸 길이를 줄여 꼬리가 위치한 칸을 비운다. 즉, 몸 길이는 유지된다.
- 특정 시간이 지나면, 뱀은 왼쪽(L)이나 오른쪽(D)으로 90도 회전한다.
사과의 위치, 뱀의 이동 경로가 주어질 때, 이 게임이 몇 초에 끝나는지 계산하라.
풀이
우리가 자주 사용하는 큐 자료구조는 선입선출 구조이다. 즉, 항상 뒤쪽으로 원소를 삽입(push)하며, 먼저 들어간 원소부터 앞쪽에서 삭제(pop)된다.
반면에, deque(덱) 자료구조는 앞, 뒤에서 push, pop 연산을 모두 수행할 수 있다.
이 문제는 뱀의 머리가 움직일 때, 꼬리가 따라오는 경우가 있고 그렇지 않은 경우가 있다. 더 구체적으로 말하면, 사과를 먹으면 머리만 움직이고 몸통과 꼬리의 위치는 유지된다. 반면에, 사과가 없는 빈 공간이면, 뱀의 머리가 나아감과 동시에 꼬리는 사라지게 된다.
따라서, 이러한 뱀의 머리와 꼬리 위치를 deque으로 관리하는 것은 꽤 괜찮은 방법이 될 수 있다.
이제 조건을 하나씩 따지며 뱀을 움직여보자. 빈칸은 0, 사과는 1, 뱀은 2로 보드판에 표시하였다. (이넘 클래스 이용)
가장 먼저 뱀은 (0, 0)에서 시작하므로 (0, 0)을 deque에 넣고, board[0][0] = 2 로 뱀의 위치를 표시하자.
뱀은 현재 방향대로 매초에 한칸씩 전진한다. 이 과정에서 고려해야 할 점은 다음과 같다.
- 움직인 좌표가 보드판의 범위를 벗어나거나 뱀의 몸통이 위치한 곳이라면?
- 움직인 좌표가 아무것도 없는 빈 공간이라면?
- 움직인 좌표가 사과가 있는 곳이라면?
- 현재 시간이 뱀이 방향을 바꾸는 시간이라면?
1번은 문제의 조건대로 게임을 종료시키면 된다.
2번은 뱀의 머리가 한칸 나아가고, 꼬리는 사라지게 된다. 즉, deque와 보드판에 대해 다음과 같은 연산을 수행한다.
board[nx][ny] = 2; // 머리 이동
auto tail = dq.back();
board[tail.first][tail.second] = 0; // 꼬리 이동
dq.pop_back(); // 꼬리 위치 제거
dq.push_front(nx, ny); // 머리 위치 삽입 3번은 꼬리는 가만히 있고, 머리만 한칸 나아가면 된다.
board[nx][ny] = 2; // 머리 이동
dq.push_front(nx, ny); // 머리 위치 삽입 4번은 현재 시간과 입력 받은 시간을 비교하여 같다면, 뱀이 바라보는 방향만 바꿔주면 된다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <deque>
using namespace std;
typedef pair<int, int> pii;
const int MAX = 101;
int N, K, L;
int board[MAX][MAX];
vector<pair<int, char>> v;
// 위의 그림 참고
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};
enum Board {
BLANK,
APPLE,
SNAKE
};
void input() {
cin >> N >> K;
// 사과 위치 초기화
for(int i = 0; i < K; i++){
int x, y;
cin >> x >> y;
// ⭐️ -1 해줘야 한다는 것에 유의!
board[x - 1][y - 1] = APPLE;
}
// 뱀의 방향 전환 정보
cin >> L;
for(int i = 0; i < L; i++){
int t;
char d; // ⭐️ int가 아니라 char 타입임에 유의!
cin >> t >> d;
v.push_back({t, d});
}
}
void solution() {
deque<pii> dq; // 뱀의 머리와 꼬리 위치 저장
// 뱀의 초기 위치와 방향
int x = 0, y = 0;
int dir = 2;
// 덱과 보드판 초기화
dq.push_back({x, y});
board[x][y] = SNAKE;
// 현재 시간 초기화
int time = 0;
int idx = 0;
// 게임 진행
while(true){
time++;
// 현재 방향에 따라 다음 위치 구하기
int nx = x + dx[dir];
int ny = y + dy[dir];
// 보드판을 벗어나거나 뱀의 몸통과 겹치면 게임 종료
if(nx < 0 || nx >= N || ny < 0 || ny >= N) break;
if(board[nx][ny] == SNAKE) break;
// 빈 공간인 경우 (머리와 꼬리 모두 이동)
if(board[nx][ny] == BLANK){
board[nx][ny] = SNAKE; // 머리 이동
auto tail = dq.back();
board[tail.first][tail.second] = BLANK; // 꼬리 이동
dq.pop_back(); // 꼬리 위치 제거
dq.push_front({nx, ny}); // 머리 위치 삽입
}
// 사과가 있는 경우 (머리만 이동)
else if(board[nx][ny] == APPLE) {
// 머리 이동
board[nx][ny] = SNAKE;
// 머리 위치 삽입
dq.push_front({nx, ny});
}
// 뱀의 방향 갱신
if(idx < v.size()){
if(time == v[idx].first) {
if(v[idx].second == 'L'){
dir = (dir + 3) % 4;
}else{
dir = (dir + 1) % 4;
}
idx++;
}
}
// 뱀의 위치 갱신
x = nx;
y = ny;
}
cout << time;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
input();
solution();
return 0;
}
