[구현][삼성기출]백준3190번 뱀

백준3190번 뱀

문제에서 요구하는 그대로 구현하면 되는 문제였다.

우선 뱀은 구현의 편의를 위해 구조체를 이용하였다.

struct snake{
    pair<int,int> head;
    list<pair<int, int> > p;
    // 0 : up,  1: right, 2: down, 3: left
    int dir;
};

뱀은 자신의 머리 위치를 나타내는 pair 변수와, 머리의 방향을 나타내는 변수 dir를 가진다.

dir은 x, y iteration 배열을 이용하여 0, 1, 2, 3으로 네 방향을 나타낼 수 있도록 하였다.

int y_iter[4] = {-1,0,1,0};
int x_iter[4] = {0,1,0,-1};

뱀이 어디에 있는지 나타내기 위해서 list 를 사용하였다. bool형 배열을 이용해 전체 map에서 뱀이 있는 곳을 나타낼 수 있지만, 이 경우 꼬리에 대한 정보가 추가적으로 필요하기 때문에 구현의 편의를 위해 list도 추가적으로 이용했다. 뱀의 머리는 list의 back에, tail 은 front에 위치하게 된다.

bool isSnake[105][105];
bool isApple[105][105];

뱀이 있는 곳은 isSnake 배열로, 사과가 있는 곳은 isApple 배열로 관리하도록 하였다.

struct snake s;
    s.head.first = 1;
    s.head.second = 1;
    s.dir = 1;
    s.p.push_back(make_pair(1,1));

    isSnake[1][1] = true;
    
    int sec = 1;
    int turnIdx = 0;

시뮬레이션에 앞서 초기화 하는 부분이다.

뱀 구조체를 생성하고, head의 위치를 1,1로 설정한다. (초기 위치가 1,1이기 때문에)

초기에 머리의 방향은 오른쪽을 향하고 있기 때문에 s.dir은 1로 설정했다.

list에 초기 위치를 넣어 뱀의 위치 정보를 포함하였다.

또, boolean 배열에 isSnake[1][1]를 true로 바꾸어 뱀이 있는 곳을 표시해주었다.

뱀의 방향 전환 정보가 초 단위로 주어지기 때문에 게임 시작부터 초 정보를 관리해줘야 한다. 따라서 시간 변수를 만들고 1로 초기화 하고, 회전 정보는 오름차순으로 주어지기 때문에 회전 정보를 담을 배열의 포인터로 사용할 변수를 만들어준다

while(1){
        //몸길이를 늘려 머리를 다음 칸에 위치시킨다.
        s.head.first += y_iter[s.dir];
        s.head.second += x_iter[s.dir];
        if(isSnake[s.head.first][s.head.second]) break;
        if(s.head.first < 1 || s.head.first >N || s.head.second <1 || s.head.second >N){
            break;
        }
        s.p.push_back(make_pair(s.head.first,s.head.second));
        isSnake[s.head.first][s.head.second] = true;
        // 사과가 있으면
        if(isApple[s.head.first][s.head.second]){
            isApple[s.head.first][s.head.second] = false;
        }
        else{
            pair<int,int> tmp = s.p.front();
            isSnake[tmp.first][tmp.second] = false;
            s.p.pop_front();
        }
        
        if(turnIdx < L && sec == turn[turnIdx].first){
            if(turn[turnIdx].second == 'D'){
                s.dir++;
                if(s.dir>3){
                    s.dir -= 4;
                }
            }
            else{
                s.dir--;
                if(s.dir <0){
                    s.dir += 4;
                }
            }
            turnIdx++;
        }
        sec++;
    }

시뮬레이션은 뱀의 머리를 다음 칸에 위치시키고, 새로 이동한 칸이 종료조건에 해당하는지 먼저 확인한다.

종료 조건에 해당하지 않을 경우 두 가지 경우로 나눠서 처리한다.

1. 사과가 있는 경우

   해당 칸의 사과를 먹은 것으로 처리하고 넘어간다.

2. 사과가 없는 경우

   꼬리가 있던 칸의 정보를 false로 업데이트 하고 list의 front를 pop 해 꼬리 정보를 업데이트 한다.

그리고 회전 정보를 처리해야 한다.

만약 회전 정보가 담긴 배열의 현재 인덱스의 초 정보가 현재와 같다면, 해당 정보에 맞게 뱀을 회전시킨다.

D 인 경우 오른쪽으로 회전이기 때문에 dir를 증가시켜야 하고, L 인 경우 왼쪽으로 회전이기 때문에 dir를 감소시켜야 한다.

#include <iostream>
#include <vector>
#include <list>

using namespace std;


int y_iter[4] = {-1,0,1,0};
int x_iter[4] = {0,1,0,-1};

bool isSnake[105][105];
bool isApple[105][105];


struct snake{
    pair<int,int> head;
    list<pair<int, int> > p;
    // 0 : up,  1: right, 2: down, 3: left
    int dir;
};

int N,K,L;
pair<int,int> apples[105];
pair<int,char> turn[105];

int main(){
    cin >> N >> K;
    for(int i=0;i<K;i++){
        int y,x;
        cin >> y >> x;
        apples[i].first  = y;
        apples[i].second = x;
        isApple[y][x] = true;
    }
    cin >> L;
    for(int i=0;i<L;i++){
        int sec;
        char dir;
        cin >> sec >> dir;
        turn[i].first = sec;
        turn[i].second = dir;
    }
    struct snake s;
    s.head.first = 1;
    s.head.second = 1;
    s.dir = 1;
    s.p.push_back(make_pair(1,1));

    isSnake[1][1] = true;
    
    int sec = 1;
    int turnIdx = 0;
    
    while(1){
        //몸길이를 늘려 머리를 다음 칸에 위치시킨다.
        s.head.first += y_iter[s.dir];
        s.head.second += x_iter[s.dir];
        if(isSnake[s.head.first][s.head.second]) break;
        if(s.head.first < 1 || s.head.first >N || s.head.second <1 || s.head.second >N){
            break;
        }
        s.p.push_back(make_pair(s.head.first,s.head.second));
        isSnake[s.head.first][s.head.second] = true;
        // 사과가 있으면
        if(isApple[s.head.first][s.head.second]){
            isApple[s.head.first][s.head.second] = false;
        }
        else{
            pair<int,int> tmp = s.p.front();
            isSnake[tmp.first][tmp.second] = false;
            s.p.pop_front();
        }
        
        if(turnIdx < L && sec == turn[turnIdx].first){
            if(turn[turnIdx].second == 'D'){
                s.dir++;
                if(s.dir>3){
                    s.dir -= 4;
                }
            }
            else{
                s.dir--;
                if(s.dir <0){
                    s.dir += 4;
                }
            }
            turnIdx++;
        }
        sec++;
    }
    
    cout << sec;
    
}