[백준] 3190 뱀

3190번: 뱀

 

www.acmicpc.net

풀이

일반적으로 생각하는 스네이크 게임과 달리 이 문제에서는 머리를 이동시키고 나서 사과가 없으면 꼬리를 지우므로 이 부분을 유의해서 종료조건을 생각해야한다. 구현하기 편하게 하기 위해서 사과는 좌표값을 키로 하여 set에 저장하였고, 뱀의 몸통은 list에 저장해서 구현하였다. 그리고 방향은 시간을 키로 하여 map에 저장하여 구현하였다.

코드

#include <iostream>
#include <set>
#include <list>
#include <map>
using namespace std;

int n, k, l;
int sx = 1, sy = 1, dir = 0;
list<pair<int, int>> snake;
set<pair<int, int>> apple;
map<int, char> cmd;
const int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };

bool is_finished() {
    // 보드를 벗어나면 게임 종료
    if (sx < 1 || sx > n || sy < 1 || sy  > n) return true;
    for (auto body : snake) 
        // 머리가 몸통에 닫으면 게임 종료
        if (sx == body.first && sy == body.second) return true;
    return false;
}

int simulation() {
    int time = 0;
    while (true) {
        time++;
        // 이전에 머리부분을 몸통의 맨 앞으로 저장
        snake.push_front({ sx, sy });
        // 머리를 한 칸 옮겨준다
        sx += dx[dir]; sy += dy[dir];

        // 종료조건 확인
        if (is_finished()) break;

        // 사과가 있는지 확인하고 사과가 있으면 사과를 제거한다
        if (apple.find({ sx, sy }) != apple.end()) apple.erase({ sx, sy });
        // 사과가 없으면 꼬리를 삭제한다
        else snake.pop_back();

        // 방향을 바꿀 시간인지 확인한다
        if (cmd.find(time) != cmd.end()) {
            if (cmd[time] == 'D') dir = (dir + 1) % 4;
            else dir = (dir - 1 + 4) % 4;
        }
    }
    return time;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    cin >> k;
    for (int i = 0; i < k; i++){
        int tmp1, tmp2;
        cin >> tmp1 >> tmp2;
        apple.insert({ tmp2, tmp1 });
    }
    cin >> l;
    for (int i = 0; i < l; i++) {
        int tmp;
        char c;
        cin >> tmp >> c;
        cmd[tmp] = c;
    }
    cout << simulation() << '\n';
    return 0;
}