3190 뱀

문제 링크

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

풀이

보드 정보를 담을 배열 arr, 뱀 정보를 담을 deque snk, 현재 시간을 나타낼 정수 now, 방향을 담을 정수 dir가 필요하다.
나머지는 주어진 조건대로 입력받으면 된다.
arr에서 사과가 있는 칸은 1, 없는 칸은 0이다.
X, C를 한 줄씩 입력받으면서 적용시킨다.
move 함수에서는 X초까지 뱀을 움직인다.
만약 움직이는 도중 벽과 부딪히거나(즉, 이동하려는 칸이 주어진 보드를 벗어남, arr[r][c] < 1 또는 arr[r][c] > N) 뱀이 자기 자신의 몸과 만나게 되는 경우(이동하려는 칸 r,c가 이미 snk에 존재함 algorithm의 find 함수 사용) 즉시 게임이 종료되므로 현재 시간 now를 출력하고 함수를 종료한다.
이동하려는 칸에 사과가 있으면(arr[r][c] == 1) snk의 front에 칸을 추가한다.
사과가 없으면 snk의 front에 칸을 추가하고 꼬리를 이동시키기 위해 pop_back()한다.
이후 now++를 하여 현재 시간을 1 늘려준다.
X초까지 종료되지 않고 이동이 끝났으면 turn에서 dir 값을 변경시켜준다.
X, C를 입력받는 중에 함수가 종료되지 않았다면 아직 더 이동할 칸이 있을 수도 있으므로 마지막에 move(10001,'A');를 통해 끝까지 이동시켜준다. 10001은 임의의 큰 수이다.

C++ 코드

#include <iostream>
#include <deque>
#include <algorithm>
#define endl '\n'
#define MAX 101

using namespace std;

int N, K, L;
int arr[MAX][MAX];
// 0:오른쪽 1:아래 2:왼쪽 3:위
int dir = 0, now = 1;
deque<pair<int, int>> snk;

void turn(char C){
    if(C == 'L'){
        dir--;
        if(dir < 0) dir = 3;
    }
    else{
        dir++;
        if(dir > 3) dir = 0;
    }
}

int move(int X, char C){
    while(now <= X){
    	int r = snk.front().first;
		int c = snk.front().second;
        if(dir == 0){
            c++;
            if(c < 1 || c > N || find(snk.begin(), snk.end(), make_pair(r, c)) != snk.end()){
                cout<<now<<endl;
                return -1;
            }
            if(arr[r][c] == 0){
                snk.push_front(make_pair(r,c));
                snk.pop_back();
            }
            else if(arr[r][c] == 1){
            	arr[r][c] = 0;
                snk.push_front(make_pair(r,c));
            }
        }
        else if(dir == 1){
            r++;
            if(r < 1 || r > N || find(snk.begin(), snk.end(), make_pair(r, c)) != snk.end()){
                cout<<now<<endl;
                return -1;
            }
            if(arr[r][c] == 0){
                snk.push_front(make_pair(r,c));
                snk.pop_back();
            }
            else if(arr[r][c] == 1){
            	arr[r][c] = 0;
                snk.push_front(make_pair(r,c));
            }
        }
        else if(dir == 2){
            c--;
            if(c < 1 || c > N || find(snk.begin(), snk.end(), make_pair(r, c)) != snk.end()){
                cout<<now<<endl;
                return -1;
            }
            if(arr[r][c] == 0){
                snk.push_front(make_pair(r,c));
                snk.pop_back();
            }
            else if(arr[r][c] == 1){
            	arr[r][c] = 0;
                snk.push_front(make_pair(r,c));
            }
        }
        else{
            r--;
            if(r < 1 || r > N || find(snk.begin(), snk.end(), make_pair(r, c)) != snk.end()){
                cout<<now<<endl;
                return -1;
            }
            if(arr[r][c] == 0){
                snk.push_front(make_pair(r,c));
                snk.pop_back();
            }
            else if(arr[r][c] == 1){
            	arr[r][c] = 0;
                snk.push_front(make_pair(r,c));
            }
        }
        now++;
    }
    turn(C);
    return 0;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>N>>K;
    for(int i=0; i<K; i++){
        int r, c;
        cin>>r>>c;
        arr[r][c] = 1;
    }
    cin>>L;
    snk.push_front(make_pair(1,1));
    for(int i=0; i<L; i++){
        int X;
        char C;
        cin>>X>>C;
        int tmp = move(X, C);
        // X초 전까지 움직임
        if(tmp == -1) return 0;
    }
    move(10001,'A');
    
    return 0;
}