문제 요약(의역)
2차원 배열 내에서의 뱀의 움직임을 시뮬레이션 하세요!
뱀은 방향을 갖습니다. 방향 커맨드는 이동 후 초가 지나면 받습니다(의역)
게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
입력
- 2차원 배열 맵의크기 N, 사과의 개수 K
- K줄에 걸쳐 사과의 위치 i, j
- 방향 전환 커맨드의 개수 L
- L줄에 걸쳐 X초 후에 적용될 방향 전환 커맨드(시간 순 정렬 된 채로 들어옴)
출력
- 게임이 몇 초 뒤에 끝날지
아이디어
그냥 규칙을 구현하면서 시뮬레이션을 해줬다.
헷갈렸던 점
1. 커맨드가 들어오는 시점
(0초) ---이동---- 1초 끝 직전에 방향커맨드(1초)
문제 상 게임 시작 시간으로부터 X초가 끝난 뒤에 커맨드가 들어온 거라고 해서
이렇게 구현을 했다.
2. 충돌
사실 나의 착각?? 땜에 헷갈렸던 부분이다. 나도 말로 하려니 이상한데 충돌이라 하면 벽에 수직한 방향으로 벽 바로 앞에 멈춰섰을 때(.....)라고 생각했다. 벽이랑 같은 방향으로 벽 코앞에서 뱀이 흘러가는 건 괜찮고.. ㅋㅋㅋㅋㅋㅋ...먼가 뱀이 이동방향쪽으로 충격파를 쏜다고 착각한 거 같다;;;
나랑 비슷한 착각을 한 사람은 없겠지만..
3. 꼬리가 줄어들고 나서 충돌 검사 vs 꼬리가 줄기 전 충돌 검사
당연히 후자다. 머리 한칸 앞으로 -> 사과 검사-> 사과 없으면 줄어듦
과정에서 사과검사 할 때 꼬리와 충돌한 것도 충돌이 맞다고 생각했다.
전자로 구현했을 땐 문제의 3번 테케에서 틀렸었다.
삽질
사과를 먹으면 사과가 없어져야하는데 그걸 빼먹고 사과 없으면 몸이 줄어듦만 구현했다..
소스코드
#include<iostream>
#include<list>
#include<queue>
#include<memory.h>
using namespace std;
//뱀을 리스트로 표현 -> 사과먹을 때 / 못먹었을 때 추가가 용이하다
//움직일 때는 그냥 안에 내용물을 그대로 둬도 됨
struct pos {
int i, j;
};
struct com {
int x;
char c;
};
int n;
bool tab[101][101];
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
int update_d(int d, char c) {
if (c == 'L') {
return ((d - 1) + 4) % 4;
}
else {
return (d + 1) % 4;
}
}
bool is_col_me(list<pos>& snake) {
pos head = snake.front();
for (list<pos>::iterator it = ++snake.begin(); it != snake.end(); it++) {
if (it->i == head.i && it->j == head.j) {
return true;
}
}
return false;
}
bool is_col_wall(pos new_head) {
if (new_head.i >= 1 && new_head.i <= n && new_head.j >= 1 && new_head.j <= n) {
return false;
}
return true;
}
/*
void print_snake(list<pos>& snake, int d) {
int marking[101][101];
memset(marking, 0, sizeof(marking));
cout << "dir : " << d << endl;
int ctr = 1;
for (list<pos>::iterator it = snake.begin(); it != snake.end(); it++) {
cout << "(" << it->i << "," << it->j << ")\t";
marking[it->i][it->j] = ctr++;
}
cout << endl << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << marking[i][j] << " ";
}
cout << endl;
}
cout << endl << endl << endl;
}
*/
int main() {
int k;
cin >> n>>k;
memset(tab, 0, sizeof(tab));
for (int ctr = 0; ctr < k; ctr++) {
int i, j;
cin >> i >> j;
tab[i][j] = true;
}
int l;
cin >> l;
queue<com> commands;
for (int i = 0; i < l; i++) {
int x;
char c;
cin >> x >> c;
commands.push(com{ x,c });
}
int time = 0;
list<pos> snake;
int d=1;//오른쪽
snake.push_front(pos{ 1,1 });
//cout << "처음 조건 : " << !is_col_me(snake) <<","<< !is_col_wall(snake.front()) <<","<< (time <= 10000) << endl;
//시간이 다 되는 경우에 대해선 명시 안돼잇음
while (true) {
pos head = snake.front();
pos new_head = pos{head.i+di[d],head.j+dj[d]};
snake.push_front(new_head);
//초가 지남
time++;
if (is_col_wall(snake.front()) || is_col_me(snake)) {
break;
}
if (tab[new_head.i][new_head.j] == false) {//사과 없으면 줄어듦
snake.pop_back();
}
else {//사과를 먹으면 없어지는 거 빠트림
tab[new_head.i][new_head.j] = false;
}
//방향 커맨드를 받음
if (!commands.empty()) {
com cur = commands.front();
if (cur.x == time) {
commands.pop();
d = update_d(d,cur.c);
}
}
//cout << "cur time :" << time << endl;
//print_snake(snake, d);
}
cout << time << endl;
}