[백준/BOJ] 3190번 뱀 (C++)

www.acmicpc.net/problem/3190

3190번: 뱀

삼성 역량 테스트 기출 문제 : 시뮬레이션(구현)

시간이 지남에 따라 바뀌는 뱀 머리 x좌표와 y좌표를 배열에 기록하는 것이 포인트인 문제입니다. 이때 시간을 뱀 꼬리 인덱스로 두어 뱀이 사과를 먹지 못할 때 뱀 꼬리 인덱스로 이전의 머리 좌표에 접근하여 꼬리가 위치한 칸을 비워줄 수 있습니다.

 

#include <iostream>
using namespace std;

const int MMAX = 102;
const int CMAX = 10002;

int map[MMAX][MMAX];
int snake_x[CMAX], snake_y[CMAX];
char cmd[CMAX];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int n, k, m, time;

void move(int dir) {
    // 머리의 x좌표, y좌표, 꼬리의 인덱스(==시간)을 선언,
    // 시간에 따른 x좌표와 y좌표를 기록 후 현재 위치에 뱀이 있음을 -1로 표현
    int head_x = 1, head_y = 1, tailIdx = time; // tailIdx == time == 0
    snake_x[time] = head_x;
    snake_y[time] = head_y;
    map[head_x][head_y] = -1;
    
    while(1) {
        time++;
        head_x += dx[dir];
        head_y += dy[dir];
        
        // 뱀의 머리가 map 범위를 벗어나거나 자기 자신과 부딪힌 경우 종료
        if(head_x < 1 || head_x > n || head_y < 1 || head_y > n) break;
        if(map[head_x][head_y] == -1) break;
        
        snake_x[time] = head_x;
        snake_y[time] = head_y;
        
        // 사과를 못먹는 경우, tailIdx를 통해 꼬리 좌표를 가져와서 해당 위치를 0으로 바꿈
        if(map[head_x][head_y] == 0) {
            int tail_x = snake_x[tailIdx];
            int tail_y = snake_y[tailIdx];
            map[tail_x][tail_y] = 0;
            tailIdx++;
        }
        
        map[head_x][head_y] = -1;
        
        // 특정 시간에 방향 이벤트 발생, D는 오른쪽으로 90도, L은 왼쪽으로 90도 회전
        if(cmd[time] == 'D') dir = (dir + 1) % 4;
        if(cmd[time] == 'L') dir = (dir + 3) % 4;
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>k;
    for(int i = 0; i < k; i++) {
        int x, y;
        cin>>x>>y;
        map[x][y] = 1; // 사과가 있는 좌표를 1로 표시
    }
    
    cin>>m;
    for(int i = 0; i < m; i++) {
        int x;
        char c;
        cin>>x>>c;
        cmd[x] = c;
    }
    
    move(0);
    cout<<time;
}