문제 이해 단계
해당 문제에서 나오는 게임은 옛날에 해봤던 게임이어서
문제를 이해하는 데는 오래 걸리지 않았다.
다만 몇몇 포인트들에 관해서만 유의 깊게 살펴봤는데,
첫 번째는 뱀이 이동하는 과정에서 머리 먼저 움직이고 꼬리가 줄어든다는 점이다.
두 번째는 보드의 크기가 100을 넘지 않는다는 점을 유의 깊게 봤다.
문제 접근 단계
이 문제의 구현을 위해
여러 가지 섹터로 나누어서 생각했다.
1. 실행이 끝나는 경우(게임오버)
게임오버가 되는 경우는 크게 두 가지가 있다.
첫 번째는 벽에 닿았을 때인데,
이걸 구현하는 것 뱀의 머리 위치가 N보다 크면 게임오버
구현하는 것은 간단하다고 생각했다.
두 번째 자기 몸에 닿았을 경우인데, 이 경우가 생각하기에 좀 복잡했다.
왜냐하면 몸길이가 늘어날 수도 있기 때문에
해당 위치에 뱀이 있는지 판단하기가 어려웠다.
처음에는 큐를 사용해서, (행, 열) 쌍으로 이루어진 요소를 넣어
머리가 이동할 때마다 이를 비교하려고 했는데,
큐에는 내부요소를 모두 비교하려면 코드도 길어지고 시간도 오래 걸린다.(시간초과)
그래서 다른 방법을 찾아보았다.
그래서 큐 대신 연결리스트를 사용하기로 했다.
연결리스트는 검색이 빨라서 시간초과가 안뜰 것 같았다.
2. 뱀 방향전환
방향전환을 하는 방식으로
0,1,2,3 네 가지 방위를 두고 D는 +1, L는 -1을 했다.
이는 간단하게 360도가 있을 때, D나 L이 나올 때마다
+-90도를 해주는 것과 비슷하다.
그래서 방향이 바뀔 때마다 움직일 방향을 정의해 줬다.
3. 사과위치 설정 및 충돌 체크
처음에는 사과 위치정보도 행렬쌍으로 만들어서 이를 비교하려고 했다.
근데 이 방식으로 하면 움직일 때마다
사과 위치정보들과 비교해줘야 해서 시간초과가 뜰 것 같았다.
그래서 배열의 크기가 100 이하이므로
2차원배열 100 * 100을 bool형으로 만든다.
배열의 값은 사과가 있는 위치의 정보를 true, 나머지는 false로 해둬서
이동할 위치의 (행, 열) 정보를 배열에 넣어 이를 빠르게 확인할 생각이다.
문제 구현 단계
0. 전역 변수 설정
static int N; // 보드 크기
static int cntRow = 1; // 행
static int cntCol = 1; // 열
static int cntDir = 0; // 바라보는 방향
static int realTime = 1; // 시간 경과
static bool apples[101][101]; // 사과 위치정보
static list<pair<int, int>> snake; // 뱀의 현재 위치함수를 통해 뱀을 움직이고 게임오버를 체크할 것이기 때문에
공용으로 사용할 변수인 보드 크기, 현재 뱀 머리의 행렬 정보,
현재 뱀이 바라보는 방향, 시간 흐름을 전역변수로 선언했다.
사과의 위치를 직관적으로 나타내기 위해
사과 배열을 101 * 101 배열을 만들었다.
인덱스가 101인 이유는 row와 col 값은 1부터 시작하기 때문에
비교할 때마다 -1 해주기 귀찮아서 이렇게 만들었다.
시간은 어떤 함수에서든 동일하게 흘러야 하기 때문에
realTime이라는 시간을 세는 전역변수를 선언했다.
마지막으로, 뱀의 위치정보를 저장할 연결리스트를 선언해 줬다.
요소 정보로는 (행, 열) 쌍을 요소로 갖도록 하였다.
1. 방향 전환과 게임오버체크
void rotate(char dir) {
switch (dir) {
case 'L':
cntDir = (cntDir - 1 >= 0) ? cntDir - 1 : 3;
break;
case 'D':
cntDir = (cntDir + 1 <= 3) ? cntDir + 1 : 0;
break;
}
}
bool isGameOver(int row, int col) {
if (row < 1 || row > N) return true;
else if (col < 1 || col > N) return true;
if (snake.end() != find(snake.begin(), snake.end(), make_pair(row, col))) return true;
return false;
}방향을 바꾸는 함수는 간단하다.
입력이 L일 경우 -1을 해주는데
0도의 -90도는 270도 이기 때문에 0 -> 3으로 바꾸는 로직을 짜줬다.
입력이 D일 경우도 마찬가지다.
3 -> 0으로 가는 로직을 짜줬다.
게임오버를 체크하는 isGameOver의 매개변수로 이동할 (행, 열) 정보를 받은 후
해당 row와 col이 설정해 뒀던 보드를 벗어날 경우 true
또한 해당 위치가 뱀이 이미 있는 곳일 경우, true를 반환해 준다.
위와 같이 비교를 해주면 뱀의 몸통에 부딪히든
꼬리에 부딪히든 모두 확인할 수 있는데
왜 이렇게 되는지는 move함수에서 설명하겠다.
2. 뱀 이동
bool move(){
switch (cntDir) {
//오른쪽 방향
case 0:
cntCol++;
break;
//아래 방향
case 1:
cntRow++;
break;
//왼쪽 방향
case 2:
cntCol--;
break;
//위쪽 방향
case 3:
cntRow--;
break;
}
if (isGameOver(cntRow, cntCol)) return false;
else {
snake.push_front(make_pair(cntRow, cntCol));
if (!apples[cntRow][cntCol]) snake.pop_back();
else apples[cntRow][cntCol] = false;
return true;
}
}뱀을 움직이는 함수 move()이다.
일단 방향에 따라 상하좌우를 확인하여 움직인다.
이는 이차원배열을 떠올리면 금방 이해될 것이다.
이후 움직일 위치를 isGameOver() 함수로 넘겨 게임오버인지 체크하고,
게임오버가 됐다면 false를 반환하고 함수를 끝낸다.
왜 false를 반환하는지는 main 함수에서 설명하겠다.
그게 아니면 연결리스트 front 부분에
이동할 위치의 (행, 열) 쌍 정보를 넣는다.
그리고 해당위치에 사과가 있는지 체크하고 사과가 있다면
몸의 길이가 늘어난 것이기 때문에 꼬리는 이동하지 않는다.
하지만 사과가 없다면 몸의 길이가 늘어난 것이 아니기 때문에
꼬리가 있던 위치 (행, 열) 쌍의 요소는 삭제한다.
이 부분이 이해가 잘 안 될 텐데, 예를 들어 설명해 보자.
뱀의 길이가 1이고 (1,1) -> (1,2)로 이동한다고 생각해 보자
(1,2)에 사과가 없는 경우 몸의 길이는 늘어나지 않기 때문에
현재 뱀의 좌표는 (1,2)가 되어야 한다.
그렇기 때문에 연결 리스트에서는 (1,1), (1,2) 좌표가 둘 다 들어가게 되고
여기서 (1,1)를 없애줘야 한다.
(1,2)에 사과가 있는 경우는 몸의 길이가 2로 늘어나기 때문에
(1,1), (1,2)가 연결리스트에 존재하게 된다.
이렇게 하면 뱀의 좌표와 길이를 쉽게 나타낼 수 있게 된다.
3. 시간에 따른 함수 구현
bool finish = false;
snake.push_front(make_pair(cntRow,cntCol));
for (int i = 0; i < L+1; i++) {
int second = -1;
char dir;
if(i != L) cin >> second >> dir;
while (realTime != second + 1) {
realTime++;
bool isEnd = move();
if (!isEnd) {
finish = true;
break;
}
}
if (finish) break;
rotate(dir);
}
realTime--;
cout << realTime << "\n";main 함수 부분인데 C++에서는
루프에 이름을 지어 한번에 탈출할 수 없기 때문에
원하는 반복문을 탈출하기 위해 finish 플래그를 만들어뒀다.
어차피 1초에는 오른쪽(1,1)으로 이동하기 때문에
임의로 (1,1) 요소를 리스트에 넣고 시작했다.
그렇기 때문에 맨 처음 realTime을 초기화할 때 1로 설정했다.
명령어를 입력받을 때 입력받는 명령어 개수 L보다
한번 더 반복시켜 주는 이유는 명령어를 다 입력한다고 해서
뱀이 움직임을 멈추는 것은 아니기 때문이다.
그래서 i값이 L과 같으면 더 이상 입력을 받지 않고 실행만 한다.
그래서 second = -1로 초기화해 줘서 입력을 받지 않은 경우
while문이 무한루프 되도록 작성했다.
만약 명령어가 '3 D' 이면, 3초 뒤에 방향이 전환돼야 하는 것이다.
즉, realTime이 3초까지는 move()를 호출해 뱀을 움직이는데
이때 move()가 false를 반환한다는 것은
isGameOver이 true라는 뜻이다.
따라서 finish를 true로 바꾸고 while문을 탈출한다.
만약 while문을 탈출했을 때 finish가 true라면
실행을 종료시키고 realTime을 출력한다.
그게 아니면 방향을 바꾸는 rotate를 실행한다.
이는 3D라면 3초 후에 D를 실행하는 것과 같다.
마지막에 realTime--는 솔직히 출력을 해보니까
계속 정답에 +1 되길래 그냥 귀찮아서 마지막에 realTime--를 해줬다.
... 귀찮았다.
마지막으로 해당 문제에 대한 전체 코드이다.
#include <iostream>
#include <list>
#include <utility>
#include <algorithm>
using namespace std;
static int N; // 보드 크기
static int cntRow = 1; // 행
static int cntCol = 1; // 열
static int cntDir = 0; // 바라보는 방향
static int realTime = 1; // 시간 경과
static bool apples[101][101]; // 사과 위치정보
static list<pair<int, int>> snake; // 뱀의 현재 위치
void rotate(char dir) {
switch (dir) {
case 'L':
cntDir = (cntDir - 1 >= 0) ? cntDir - 1 : 3;
break;
case 'D':
cntDir = (cntDir + 1 <= 3) ? cntDir + 1 : 0;
break;
}
}
bool isGameOver(int row, int col) {
if (row < 1 || row > N) return true;
else if (col < 1 || col > N) return true;
if (snake.end() != find(snake.begin(), snake.end(), make_pair(row, col))) return true;
return false;
}
bool move(){
switch (cntDir) {
//오른쪽 방향
case 0:
cntCol++;
break;
//아래 방향
case 1:
cntRow++;
break;
//왼쪽 방향
case 2:
cntCol--;
break;
//위쪽 방향
case 3:
cntRow--;
break;
}
if (isGameOver(cntRow, cntCol)) return false;
else {
snake.push_front(make_pair(cntRow, cntCol));
if (!apples[cntRow][cntCol]) snake.pop_back();
else apples[cntRow][cntCol] = false;
return true;
}
}
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
//전부 false로 초기화
for (int i = 0; i < 101; i++)
for (int j = 0; j < 101; j++)
apples[i][j] = false;
int K, L;
cin >> N >> K;
while (K-- > 0) {
int r, c;
cin >> r >> c;
apples[r][c] = true;
}
cin >> L;
bool finish = false;
snake.push_front(make_pair(cntRow,cntCol));
for (int i = 0; i < L+1; i++) {
int second = -1;
char dir;
if(i != L) cin >> second >> dir;
while (realTime != second + 1) {
realTime++;
bool isEnd = move();
if (!isEnd) {
finish = true;
break;
}
}
if (finish) break;
rotate(dir);
}
realTime--;
cout << realTime << "\n";
return 0;
}
시행착오
문제를 푸는데 굉장히 오래 걸렸다.
핵심적인 뱀의 움직임 부분을 생각해 내는 것은 오래 걸리진 않았는데,
알고리즘을 구현하고 사과의 위치나 여러 부분을 생각하기에는
굉장히 오래 걸렸던 것 같다.
디테일 부분을 다듬는데 너무 힘들어서, 마지막에 가서는 그냥 간단히 처리했다.
게임을 만드는 느낌이 들어서,
좀 더 열심히 만들었던 느낌이 있었다.