[BOJ] C++ 3190: 뱀 - 복잡한 조건의 시뮬레이션, 꼭 풀어보세요!!

3190번: 뱀

예제 1

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

ans : 9

예제 2

10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

ans : 21

---

뱀 게임을 시뮬레이션 돌리는 문제이다. 문제를 풀기 전 꼭 알아야 할 주의사항이 3개 정도 있는데 놓치기 굉장히 쉽고, 실제로 나도 세 사항 모두 놓쳐서 틀렸다.

1. 배열은 (1, 1)부터 시작한다. 즉, 0 index가 아니다.
2. X초가 끝난 후 방향 전환을 한다. X초에 방향 전환을 하는 것이 아니다.
3. 일단 이동 후 벽이나 뱀에 부딪혀야 종료한다. 즉 우선 이동을 시키고 벽이나 뱀이면 종료하므로 1초가 증가한 상태로 종료한다.

---

이제 어떻게 구현해야할지 가닥을 잡아보자. 나는 알고리즘을 구성할 때 꼭 구현해야 하는 사항을 먼저 적어두고 시작한다.

1. X초 후 C 방향으로 전환
   • 현재 시간을 기억해두고 몇 초에 방향 전환을 해야 하는지도 기억해 둔 다음 비교해서 전환시키면 될 것 같다.
2. 이동한 곳이 뱀이거나 벽이면 종료
3. 이동한 곳이 사과면 유지
4. 이동한 곳이 사과가 아니면 꼬리 1칸 삭제
   • 이 부분에서 꼬리 위치를 기억해야 한다는 사실을 알 수 있다. 꼬리 삭제 후 다음 꼬리를 알아야 하는데 바로 떠오르는 방법은 (a, b)에서 진행 방향을 기억해 두고 그대로 다음 꼬리를 저장해 두거나 deque를 활용하는 방법이다.
   • deque 자료구조는 자료의 앞/뒤에서 삽입, 삭제가 모두 가능한 자료구조이다. 뱀의 삽입, 삭제는 머리와 꼬리에서만 일어나므로 deque로 구성했다.

이정도 필수 구현사항이 있고 디테일한 건 구현하면서 생각하자. 이제 완전 탐색으로 할지 다른 알고리즘을 사용할지 판단하면 되는데, 딱히 떠오르는 알고리즘이 없어서 완전  탐색으로 생각해 두고 시간복잡도를 계산해 봤다. 

 

입력을 잘 보면 최악의 경우 10000초 후 마지막 방향 전환이 일어나고 보드의 최대 크기가 100이므로 10100초 안에 게임이 무조건 끝난다. 러프하게 10000초 만큼 진행하게 되는데, 완전 탐색이어도 1초 진행하는데 상수시간이 소모될 것 같아서 완전 탐색으로 구성했다. 

---

완전 탐색으로 구성한다면 일단 방향 전환 정보를 기억해야하고, 뱀의 머리가 진행한 곳이 뱀인지 사과인지 알아야 하므로 2차원 배열로 board를 짜놓았다. 뱀은 1, 사과는 2로 기록하였다. 또, 뱀의 머리와 꼬리가 어디인지 알아야 하는데 그냥 알기만 하면 안 되고 그 순서 또한 알아야 하기에(꼬리 다음 뱀 칸이 어딘지) deque로 뱀의 정보를 따로 저장했다.

 

이제 구현에 들어가보자. 1초 진행하는 함수부터 짰는데, 오른쪽 방향을 0으로 두고 시계방향으로 1씩 증가하는 방식으로 현재 머리가 가리키고 있는 방향을 기록했다. 

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int board[102][102];
deque<pair<int, int>> snake;
vector<pair<int, char>> dir;

bool simulate()
{
    // cur_dir 방향으로 1초 진행
    // 방향에 따라 머리를 한 칸 옮긴다. 머리는 snake.end에 있다.
    // 옮긴 곳이 벽이거나 뱀이면 종료
    int nx = snake.back().first + dx[cur_dir];
    int ny = snake.back().second + dy[cur_dir];
    cur_sec++;
    if (nx < 0 || nx >= n || ny < 0 || ny >= n || board[nx][ny] == 1)
        return false;

    // 옮긴 곳이 사과던 아니던 공통적으로 수행
    snake.push_back({nx, ny});

    // 옮긴 곳이 사과면 그냥 종료
    if (board[nx][ny] == 2)
    {
        board[nx][ny] = 1;
        return true;
    }

    // 옮긴 곳이 사과가 아니면 꼬리 하나 삭제. 꼬리는 snake.front에 있다.
    board[nx][ny] = 1;
    board[snake.front().first][snake.front().second] = 0;
    snake.pop_front();
    return true;
}

이것도 잡기술이 조금 들어갔는데, 처음에는 cur_dir 방향에 따라 switch문으로 짜려고 하다가 어차피 방향이 0, 1, 2, 3으로 고정되어 있으므로 dx, dy 배열을 이용해서 머리가 1초 후 진행할 칸 위치를 nx, ny로 기록했다. 나머지 부분은 처음에 구성한 그대로 구현했다.

 

이제 남은건 방향 전환뿐이다. 방향 전환은 사진을 참고하자. 나도 실제 구현할 때 똑같이 그려가면서 구현했다.

// 방향 전환해야하는지 확인
if (cur_sec == dir[dir_index].first)
{
    if (dir[dir_index].second == 'L')
    {
        cur_dir = (cur_dir + 3) % 4;
        dir_index++;
    }
    else
    {
        // 오른쪽으로 90도 회전
        cur_dir = (cur_dir + 1) % 4;
        dir_index++;
    }
}

코드를 보면 방향을 전환해야하는지 확인할 때 cur_sec == dir [dir_index]. first로 되어있다. 이렇게 구현한 이유는 dir 배열을 처음부터 탐색하면서 현재 초와 같은 초가 나올 때까지 탐색하는 것보다 어디까지 탐색했는지 dir_index로 저장해 놓고 바로 접근하면 훨씬 빠르게 탐색이 가능하다. 이런 식으로 index만 기억해 두고 배열에 접근하는 방식은 여러 알고리즘에서 굉장히 많이 사용된다. 두 코드를 합쳐주기만 하면 구현 끝이다.

/** 시뮬레이션 3190 뱀 **/
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <string>
using namespace std;

int n, k, l, cur_sec = 0, cur_dir = 0;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int board[102][102];
deque<pair<int, int>> snake;
vector<pair<int, char>> dir;

bool simulate()
{
    // cur_dir 방향으로 1초 진행
    // 방향에 따라 머리를 한 칸 옮긴다. 머리는 snake.end에 있다.
    // 옮긴 곳이 벽이거나 뱀이면 종료
    int nx = snake.back().first + dx[cur_dir];
    int ny = snake.back().second + dy[cur_dir];
    cur_sec++;
    if (nx < 0 || nx >= n || ny < 0 || ny >= n || board[nx][ny] == 1)
        return false;

    // 옮긴 곳이 사과던 아니던 공통적으로 수행
    snake.push_back({nx, ny});

    // 옮긴 곳이 사과면 그냥 종료
    if (board[nx][ny] == 2)
    {
        board[nx][ny] = 1;
        return true;
    }

    // 옮긴 곳이 사과가 아니면 꼬리 하나 삭제. 꼬리는 snake.front에 있다.
    board[nx][ny] = 1;
    board[snake.front().first][snake.front().second] = 0;
    snake.pop_front();
    return true;
}

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;
        // 사과의 위치를 2로 저장
        board[x - 1][y - 1] = 2;
    }

    cin >> l;
    for (int i = 0; i < l; i++)
    {
        int sec;
        char str;
        cin >> sec >> str;
        // 방향 전환 정보 저장
        dir.push_back({sec, str});
    }

    // 뱀 위치를 1로 저장
    board[0][0] = 1;
    snake.push_back({0, 0});
    int dir_index = 0;
    // cur_sec == dir[dir_index].first 라면 방향전환 해주기

    while (1)
    {
        // 방향 전환해야하는지 확인
        if (cur_sec == dir[dir_index].first)
        {
            if (dir[dir_index].second == 'L')
            {
                cur_dir = (cur_dir + 3) % 4;
                dir_index++;
            }
            else
            {
                // 오른쪽으로 90도 회전
                cur_dir = (cur_dir + 1) % 4;
                dir_index++;
            }
        }
        // 1초 진행
        if (!simulate())
        {
            cout << cur_sec << '\n';
            break;
        }
    }
}

시뮬레이션의 전형적인 문제였고 그만큼 구현하기 까다로운 문제였다. 특히 입력에서 board를 전혀 받지 않고있고 시간 복잡도 계산이 꽤 까다로워서 시뮬레이션으로 구현하면 시간초과가 뜰 것 같다고 생각하기 쉬워서 어려운 문제였다.