[BOJ][Gold IV] 뱀 - 3190번 (C++)

[Gold IV] 뱀 - 3190

문제 링크

3190번: 뱀

분류

자료 구조(data_structures), 덱(deque), 구현(implementation), 큐(queue), 시뮬레이션(simulation)

문제

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

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

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

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

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

입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

풀이

여친이 구현이 복잡하다고 풀어보라고 해서 풀게된 문제. 백준에 로그인을 안해서 몰랐는데 풀고나니 이미 8달전에 풀었던 문제였다.

살짝 킹받지만 8달전의 내 코드를 보니 전혀 다르게 구현했다. 그런 의미로 2가지 풀이를 진행한다.

구현 : 큐로 뱀 구현하기

첫 번째로 뱀의 움직임을 큐로 직접 구현하는 방법이다.

#include <bits/stdc++.h>
using namespace std;
int N, K, x, y, L, X;
int board[101][101];
vector<pair<int, int>> path;

void turn(int &direction, int right) {
    if(right) direction++;
    else direction--;
    if(direction == 4) direction=0;
    if(direction == -1) direction=3;
}

void go(int direction, int &x, int &y) {
    switch (direction) {
        case 0: x--; break; // left
        case 1: y--; break; // top
        case 2: x++; break; // right
        case 3: y++; break; // bottom
        default: break;
    }
}

int main() {
    cin >> N >> K;
    for(int i=0;i<K;i++) {
        cin >> y >> x;
        board[y][x] = -1;
    }
    cin >> L;
    char C;
    while(L-- && cin >> X >> C)
        if(C=='D') path.emplace_back(X, 1);
        else       path.emplace_back(X, 0);

    path.emplace_back(100001, 1);

    x = 1; y = 1;
    board[1][1] = 1;

    queue<pair<int, int>> snake;
    auto path_itr = path.begin();
    snake.push({1, 1});

    int direction = 2;
    int time = 0, t, right;

    while(true) {
        tie(t, right) = *path_itr;
        if(t == time) {
            path_itr++;
            turn(direction, right);
        }
        go(direction, x, y);
        time++;

        // 벽, 몸통 충돌
        if(x > N || x < 1 || y > N || y < 1) break;
        if(board[y][x] == 1) break;

        // 꼬리 짜름
        if(board[y][x] != -1) {
            board[snake.front().second][snake.front().first] = 0;
            snake.pop();
        }

        // 머리 집어 넣음
        board[y][x] = 1;
        snake.push({x, y});
    }

    cout << time << endl;
}

코드는 길지만 구현은 아주 직관적이다.

먼저 자료를 저장할때 사과의 위치를 NxN 보드에 마크해둔다. 그리고 몸통의 정보를 snake 큐에 pair<int, int>의 좌표로 저장할 것이다. 만약 다음 방향으로 한칸 나아가 사과의 위치라면 꼬리를 그대로 두고, 아니라면 꼬리를 잘라내는 (snake.pop()) 충실하게 구현한 코드이다.

큐의 특성에 따로 뱀의 머리부터 꼬리까지의 몸통의 위치를 좌표로써 저장할 수 있다는 점을 생각한다면 쉽게 구현가능하다.

구현 : 경로를 저장하지 않는 방법

이번에 풀 때는 큐로 푸는 법을 생각하지 못해서 나름 독특하게 풀었다. 위 방법이 뱀이 움직이는 모습을 직접 구현했다면, 아래 방법은 뱀이 지나간 경로를 시간별로 기록해두는 방법이다.

#include <bits/stdc++.h>
using namespace std;
int N, K, L, x, y, z;
typedef pair<int, int> pii;
set<pii> apples;
priority_queue<pii> direction;
vector<vector<int>> board(101, vector<int>(101, 0));

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

bool isIn(int x, int y) {
    return 0 <= x && x < N && 0 <= y && y < N;
}

void input() {
    cin >> N >> K;
    for(int i=0;i<K;i++) {
        cin >> y >> x;
        apples.insert({x-1, y-1});
    }
    char c;
    cin >> L;
    for(int i=0;i<L;i++) {
        cin >> z >> c;
        direction.push({-z, c == 'D'});
    }
}

int main() {
    input();

    int t=0, d=0, x=0, y=0;
    int len = 1;

    while(isIn(x, y)) {
        // 사과를 먹으면 몸통 길이가 늘어난다
        auto apple = apples.find({x, y});
        if(apple != apples.end()) {
            apples.erase(apple);
            len++;
        }

        // 자신의 몸통에 부딪힌다.
        if(board[y][x] != 0 && t-len <= board[y][x]) break;

        board[y][x] = t++;

        if(!direction.empty() && -direction.top().first == t-1) {
            d = direction.top().second ? (d+1)%4 : (d+3)%4;
            direction.pop();
        }

        x = x + dx[d];
        y = y + dy[d];
    }

    cout << t;

}

이번에는 사과의 위치를 다른 리스트에 저장해놨는데, 지금 생각해보니 굳이 그럴필요 없이 첫 번째 구현과 같이 보드에 -1과 같이 표기해도 될 것 같다.

일단 뱀의 머리만 x, y 로 저장하고 첫번 째와 다르게 몸통, 꼬리의 정보를 저장하지 않는다. 다만 맵에 지나갈때마다 해당 시간을 기록하고, 사과를 먹으며 늘어난 몸통의 길이를 기록한다.

가장 빠르고 간단하게 한바퀴를 돌아서 자신에 몸통에 부딪히는 경우를 생각해보자.

t=3 일때 모든칸에 사과가 있고, 매 칸마다 우회전하여 다음과 같이 진행되었다고 생각해보자.

0	1
3	2

t=4일떄 (0, 0)에 충돌하게 되는데 이때 현재 시간과 그 칸에 기록된 시간의 차이는 몸통의 길이와 비교하여 충돌여부를 결정할 수 있다.

// 자신의 몸통에 부딪힌다.
if(board[y][x] != 0 && t-len <= board[y][x]) 
    break;

소감

구현이 살짝 까다로운 문제다. 처음부터 설계를 깔끔하게 짠다면 쉽게 풀 수 있었을 것 같다.