(C++) - 백준(BOJ) 3190번 : 뱀

www.acmicpc.net/problem/3190

3190번: 뱀

deque을 이용한 시뮬레이션 문제였습니다.

 

 

📕 풀이방법

📔 입력 및 초기화

deque snake를 선언합니다. 뱀의 머리는 front(), 뱀의 꼬리는 back()이라고 생각합니다. 한 원소의 자료형은 Snake라는 x,y 좌표 정보를 가지고 있는 구조체입니다. 뱀의 몸통에 부딪혀 게임이 종료될 수 있기때문에 뱀의 형태를 모두 저장해야 하기 때문입니다.

 입력을 받습니다. 사과가 있는 위치는 1로만들어주고, map자료구조를 이용해 key : x, value : 방향이 들어가도록 합니다.

 

📔 풀이과정

 1. 게임을 시작합니다. 시간을 1씩증가시킵니다.

 

 2. 뱀의 머리를 현재 방향에 따라 뱀의 다음 위치를 정합니다.

 

 3. 뱀의 이동한 위치가 종료 조건에 맞는다면 break합니다. 지역에서 벗어나거나 뱀의 머리가 몸통을 만났을 경우가 종료 조건입니다. 

 

 4. 종료되지 않는다면 뱀의 머리가 이동합니다. push_front(다음 x, 다음 y)입니다.

 

 5. 사과가 다음 위치에 없다면 꼬리를 pop해줍니다. 사과가 있다면 사과가 있던 위치를 지워줍니다.

 

 

📔 정답출력

게임 종료 후 시간을 출력합니다.

 

---

 

 

📕 Code

#include <bits/stdc++.h>
using namespace std;
int board[101][101];

//상,우,하,좌
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};

int n,k,l,sec,flag,direction = 1;

struct Snake {int x,y;};

deque <Snake> snake;
map <int,char> m;

int main(){
    snake.push_back({1,1});
    cin >> n >> k;

    while(k--){
        int x,y;
        cin >> x >> y;
        board[x][y] = 1;
    }
    cin >> l;

    while(l--){
        int x;
        char dir;
        cin >> x >> dir;
        m[x] = dir;
    }

    while(1){
        sec++;
        int x = snake.front().x;
        int y = snake.front().y;
        int nx = x + dx[direction];
        int ny = y + dy[direction];
        for(auto &el : snake)
            if(el.x == nx && el.y == ny) 
                { flag = 1; break; }
        if(1 > nx || nx > n || 1 > ny || ny > n || flag) { flag = 1; break; }
        snake.push_front({nx,ny});
        if(!board[nx][ny]){ snake.pop_back();}
        else board[nx][ny] = 0;
        if(m[sec] == 'D') direction = (direction + 1) % 4;
        else if(m[sec] == 'L') direction = (3 + direction) % 4;
    }

    cout << sec << '\n';
}