[백준] 뱀

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

3190번: 뱀

구현 문제입니다.

 

우선 문제부터 간단하게 요약해보면, 

뱀이 과일을 먹으면 성장하고, 뱀에게는 command로 특정 초(시간) 에서 방향을 전환하라는 명령어가 떨어집니다. 이 때, 주어진 명령대로 행동 하였을 때, 뱀은 언제 죽는지를 구해야 하는 문제입니다.

 

<Solution>

구현 문제인데, 조금의 아이디어는 뱀을 queue로 관리하여 문제를 조금 더 편하게 해결이 가능합니다. 

 

실제로 grid를 만들어 길을 ' . ', 과일을 ' F ', 뱀을 ' S ' 이런 형태로 두어 디버깅과 구현을 좀더 쉽게 하였습니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <algorithm>
#include <queue>
 
using namespace std;
 
char grid[100+10][100+10];
int N;
int K;
int L;
int cur_time;
 
struct command{
    int t;
    char dir;
}CMD[100+10];
 
struct rc{
    int r, c;
};
 
// directions up right down left
int d_row[] = {-1, 0, 1, 0};
int d_col[] = {0, 1, 0, -1};
 
void InputData(){
    cin >> N;
    cin >> K;
    // build initial grid
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<= N; j++){
            grid[i][j] = '.';
        }
    }
    for(int i = 0; i<K; i++){
        int r, c;
        cin >> r >> c;
        grid[r][c] = 'F';
 
    }
    cin >> L;
    for (int i=0; i<L; i++){
        cin >> CMD[i].t >> CMD[i].dir;
    }
    CMD[L].t = 987654321;
 
    // grid 1,1 -> snake
    grid[1][1] = 'S';
}
bool compare(struct command a, struct command b){
    return a.t<b.t;
}
 
void solution(){
    // sort CMD via time
    sort(CMD, CMD+L, compare);
 
    // make snake
    queue <rc> snake;
    rc cur_head = {1,1};
    int cur_dir = 1;
    int used_cmd = 0;
 
    snake.push((rc){1,1});
     
    while(1){
 
        // 방향전환 유무 check
        while(cur_time == CMD[used_cmd].t){
            if(CMD[used_cmd].dir == 'L'){
                // 왼쪽으로 90도
                cur_dir = (cur_dir+3) % 4;
            }
            else{
                cur_dir = (cur_dir+1) % 4 ;
            }
            used_cmd+=1;
        }
 
        // head 로 부터 다음칸 확인
        int next_r = cur_head.r + d_row[cur_dir];
        int next_c = cur_head.c + d_col[cur_dir];
 
        // 외부로 나감
        if(!grid[next_r][next_c]){
            cur_time+=1;
            return;
        }
 
        // 자기 자신을 뭄
        if(grid[next_r][next_c] == 'S'){
            cur_time+=1;
            return;
        }
 
        // 과일인 경우
        if(grid[next_r][next_c] == 'F'){
            // head update
            cur_head.r = next_r;
            cur_head.c = next_c;
 
            // snake로 마킹
            grid[next_r][next_c] = 'S';
 
            // snake 길이 연장
            snake.push((rc){next_r, next_c});
            cur_time+=1;
            continue;
        }
 
        // 빈칸인 경우 ('.')
        // head update
        cur_head.r = next_r;
        cur_head.c = next_c;
 
        // snake로 마킹
        grid[next_r][next_c] = 'S';
 
        // snake 수정
        snake.push((rc){next_r, next_c});
         
        // 꼬리 잘라내기
        rc tail = snake.front(); snake.pop();
 
        // 꼬리 맵 수정
        grid[tail.r][tail.c] = '.';
        cur_time+=1;
    }
}
 
int main(){
 
    InputData();
 
    solution();
 
    cout << cur_time << endl;
    return 0;
}