[백준/C++] 3190번 뱀

문제 링크

https://www.acmicpc.net/problem/3190

3190번: 뱀

접근 방법

일반적인 시뮬레이션 문제입니다. 시뮬레이션 문제는 세부사항을 잘 읽는 것이 중요하고 해당 문제에서 구현에 유의할 점을 크게 2가지로 보았습니다.

첫 번째로는 사과를 먹었을 때의 상황,

두 번째로는 움직임과 동시에 벽과의 충돌여부 검사입니다.

사과 여부에 따른 뱀 정보 최신화, 이동하는 좌표가 벽 또는 몸이라면 즉시 게임을 종료하도록 코드를 구현하였습니다. 

추가적으로 N이 100이므로 뱀이 최대한 움직일 수 있는 시간인 10000 크기의 방향 전환 배열을 선언하고 정보를 저장하여 상수 시간안에 해당 시간에 뱀이 방향을 전환하는지 알 수 있도록 했습니다.

 

코드

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int N, K, L, r, c, X, current_dir, map[101][101], answer;
char C, dir_transition[10001];

pair<int, int> dir[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
vector<pair<int, int>> snake;

bool check_collision(int head_y, int head_x) {
    if (head_y >= N || head_x >= N || head_y < 0 || head_x < 0) return true;
    for (int i = snake.size() - 2; i >= 0; i--) {
        if (head_y == snake[i].first && head_x == snake[i].second)
            return true;
    }
    return false;
}

bool move() {
    pair<int, int> prev = snake[snake.size() - 1];
    int next_y = prev.first + dir[current_dir].first;
    int next_x = prev.second + dir[current_dir].second;
    if(check_collision(next_y, next_x)) return true;

    if (map[next_y][next_x]){
        snake.push_back(make_pair(next_y, next_x));
        map[next_y][next_x] = 0;
    }
    else {
        snake[snake.size() - 1].first = next_y;
        snake[snake.size() - 1].second = next_x;
        for (int i = snake.size() - 2; i >= 0; i--) {
            pair<int, int> tmp = snake[i];
            snake[i] = prev;
            prev = tmp;
        }
    }
    return false;
}

void check_dir_transition(){
    char c = dir_transition[answer];
    if(c == 'L') current_dir = (current_dir - 1 + 4)% 4;
    else if(c == 'D') current_dir = (current_dir + 1) % 4;
}

int solve() {
    while (true) {
        answer++;
        if(move()) return answer;
        check_dir_transition();
    }
}

int main() {
    snake.push_back(make_pair(0, 0));
    cin >> N >> K;
    for (int i = 0; i < K; i++) {
        cin >> r >> c;
        map[r - 1][c - 1] = 1;
    }
    cin >> L;
    for (int i = 0; i < L; i++) {
        cin >> X >> C;
        dir_transition[X] = C;
    }
    cout << solve();
}

 

코드 설명

뱀의 정보는 vector로 표현하였고 사과를 먹어 길이가 늘어나는 경우 머리를 push_back하여 길이를 늘리는 방식으로 하였습니다. 뱀의 이동은 사과가 있는 경우 다음 좌표를 머리로 추가하고 사과가 없는 경우는 머리를 제외한 몸통의 부분을 한칸씩 앞당겨 뱀의 정보를 최신화 하였습니다.

다만 위 부분은 vector가 아닌 queue 혹은 deque를 이용하여 가장 앞의 원소(머리)를 pop하는 것으로 더 깔끔한 처리가 가능하겠습니다.

이 외에 충돌 검사는 벽 충돌 여부와, 머리를 제외한 몸통 충돌 여부로 검사하였고

방향 전환 배열을 이용하여 상수 시간에 해당 시간에 방향 전환이 일어나는지 확인하고 mod 연산을 통해 알맞게 방향을 변경하였습니다.