백준 3190 뱀 - 앞뒤로 넣고 빼야 될 때는 deque를 활용하자!

문제 링크

www.acmicpc.net/problem/3190

풀이 아이디어

아이디어 랄건 딱히 없는데 구현을 잘 해야 풀 수 있는 문제다.

뱀의 머리와 꼬리를 이동시키고, 복제시키고 하는 로직때문에 머리꼬리를 동시에 관리해야 한다.

이럴 경우에 적합한 자료구조는 deque라고 널리 알려저 있기 때문에 deque을 사용해서 변수를 관리한다.

 

주의해야 할 점을 몇 가지 적자면

1. 뱀의 몸통이랑 부딪히는 것까지 생각을 해야 하므로 bool snake[][] 배열을 만들어, 뱀이 있는 공간은 true로 설정을 한다.

2. 명령이 L개 주어지는데, 명령이 있을 때만 명령을 읽고 처리하기 위해 if(opdq.size()) 조건이 꼭 필요하다. 

만약 명령이 담긴 deque인 opdq의 size가 0일때는 그냥 실행되지 않도록.

저 조건 없이 그냥 opdq.front()로 변수를 부를 시 에러가 생길 수 있음.

코드

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1,0,-1,0}; //동 남 서 북
int dy[4] = {0,1,0,-1};
int N,K,L;
bool apple[101][101];
bool snake[101][101];
int main() {
    cin>>N>>K;
    int x,y;
    for(int i=0; i<K; i++){
        cin>>y>>x;
        apple[y][x] = true;
    }
    cin>>L;
    int time;
    char C;
    deque<pair<int,char>> opdq;
    for(int i=0; i<L; i++){
        cin>>time>>C;
        opdq.push_back({time,C});
    }
    int sec=0;
    int idx=0;

    deque<pair<int,int>> snakedq;
    snakedq.push_back({1,1}); //(y,x) 로 저장
    snake[1][1] = true;
    while(true){
        sec++;
        pair<int,int> snakehead = snakedq.back();
        pair<int,int> newh = {snakehead.first + dy[idx], snakehead.second + dx[idx]};

        if(snake[newh.first][newh.second] || newh.first<1 || newh.first>N || newh.second<1 || newh.second>N){
            cout<<sec<<"\n";
            break;
        }
        snake[newh.first][newh.second]=true;
        snakedq.push_back(newh);
        // 사과 안먹었을 때 pop
        if(!apple[newh.first][newh.second]){
            pair<int,int> tail = snakedq.front();
            snake[tail.first][tail.second] = false;
            snakedq.pop_front();
        }
        else{
            apple[newh.first][newh.second]= false;
        }

        //방향전환
        //조심해야 할 부분1 : 명령이 있을 때만 front를 반환해야 하므로 size를 통해 미리 체크해야 한다.
        if(opdq.size()) {
            pair<int, char> frontop = opdq.front();
            if(frontop.first==sec){
                if(frontop.second=='L')
                    idx = (idx+3) %4;
                else
                    idx = (idx+1) %4;
                opdq.pop_front();
            }
        }
    }
}