문제 푼 날짜 : 2021-09-28

문제

문제 링크 : https://www.acmicpc.net/problem/3190

접근 및 풀이

어떤 자료구조를 이용해야하는지 고민을 많이 했던 문제였습니다.
평소에 알고있던 snake 게임과는 달리 이 문제에서는 사과를 먹었을 때 뱀의 만 길어지고 꼬리는 그대로 살아있고, 사과가 없는 곳을 갔을 때 꼬리가 줄어들게 됩니다.
이러한 특성을 잘 이용할 수 있는 자료구조가 deque라고 생각해서 deque를 이용하여 문제를 풀었습니다.
코드는 아래의 생각대로 구현하였다.

1. 뱀이 이동하다가 범위를 벗어나거나 자기 몸통을 만나 종료될 때까지 아래 과정을 반복한다.
2. 뱀이 (1, 1)에서 오른쪽을 향하도록 설정해준다. (뱀이 있는 곳은 2로 나타냄)
3. 사과를 먹었을 때 이동할 곳의 좌표를 push_front()한다. (머리가 이동하여 몸통이 늘어남.)
4. 사과가 없는 곳에 갔을 때 pop_back()한다. (꼬리가 줄어듦.)
5. 방향을 바꿔야하는 X초가 되면 방향을 체크하여 바꾸어준다. (changeDir 함수)

코드

// 백준 3190번 : 뱀
#include <iostream>
#include <deque>
#include <queue>

using namespace std;

#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3

int board[101][101] = { 0, };

int D[4][2] = {{ -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }};

int changeDir(int now, char dir) {
    if (dir == 'L') {
        if (now == UP) {
            return LEFT;
        } else if (now == RIGHT) {
            return UP;
        } else if (now == DOWN) {
            return RIGHT;
        } else if (now == LEFT) {
            return DOWN;
        }
    } else if (dir == 'D') {
        if (now == UP) {
            return RIGHT;
        } else if (now == RIGHT) {
            return DOWN;
        } else if (now == DOWN) {
            return LEFT;
        } else if (now == LEFT) {
            return UP;
        }
    }
    return -1;
}

int main() {
    int N, K, L;
    deque<pair<int, int>> dq;
    queue<pair<int, char>> q;
    
    cin >> N >> K;
    
    while (K--) {
        int i, j;
        cin >> i >> j;
        board[i][j] = 1; // 사과가 있는 곳
    }
    
    cin >> L;
    
    while (L--) {
        int t;
        char d;
        cin >> t >> d;
        q.push(make_pair(t, d));
    }
    
    // 처음 시작 세팅
    dq.push_back({ 1, 1 });
    board[1][1] = 2; // 뱀이 있는 곳
    int dir = RIGHT;
    int time = 0;
    
    while (true) {
        time++;
        int nextY = dq[0].first + D[dir][0];
        int nextX = dq[0].second + D[dir][1];
        
        if (nextY < 1 || nextY > N || nextX < 1 || nextX > N || board[nextY][nextX] == 2) {
            break;
        }
        
        if (board[nextY][nextX] == 1) { // 사과일 경우
            board[nextY][nextX] = 2;
            dq.push_front(make_pair(nextY, nextX));
        } else {
            board[nextY][nextX] = 2;
            dq.push_front(make_pair(nextY, nextX));
            board[dq.back().first][dq.back().second] = 0;
            dq.pop_back();
        }
        
        if (!q.empty()) {
            int turnTime = q.front().first;
            char turn = q.front().second;
            
            if (time == turnTime) {
                dir = changeDir(dir, turn);
                q.pop();
            }
        }
    }
    cout << time;
    return 0;
}

결과

피드백

deque를 이용해서 문제를 좀 풀어봐야 될 것 같다.