백준(C++) 3190 [뱀]

 

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

3190 뱀

접근방법

백준 삼성 SW 역량 기출 문제 중 하나인 뱀이다. 조금 풀어보니 앞문제가 대부분 시뮬레이션 문제였다.

이 문제도 시뮬레이션 문제이다. 시뮬레이션 문제는 주어진 상황을 정확하게 처리 해야한다. 상황에는 여러 문제가 있는데 그것이 시뮬레이션 문제의 접근방법이다. 

이 문제의 상황은 NxN 정사각형 보드 위에 뱀이 움직이는것을 구현하라는 것이다. 4가지 규칙이 있는데 그것을 고려하면서 구현하면된다.

 

보드내에서의 뱀이 움직인 시간을 구하는 거라 처음은 BFS 기반을 생각했다. 하지만 내가 자주쓰던 BFS 형식을 하니 구현이 꼬였다. 막 덱도 써보고 이상한거 다써본 결과 이 문제는 최소 이동거리를 구하는게 아니고, 뱀이 어디까지 가는지 구하는 것이기에 그랬다.

그래서 단순하게 구현했다. 허무했다.

• 빈칸은 board내 0의 값을 가짐
• 뱀은 board 내 1의 값을 가짐
• 사과는 board 내 2의 값을 가짐

1. 뱀이 범위를 넘거나 벽에 부딪치면 시간값을 리턴
2. 사과를 먹으면 뱀 큐에 지금 위치를 넣고 board에 1 입력
3. 빈칸을 간경우 뱀 큐에 지금 위치를 넣고 뱀 큐의 맨 마지막 값을 없앰 그리고 board에 1입력
4. 큐에 저장된 방향 좌표 변경 시간이 되면 방향을 이동시키고 큐 한개를 비움

이렇게 구현만 하면 끝나는 것을 완전 복잡하게 생각한 결과 2시간이나 걸려버렸다.

 

코드는 다음과 같다.

 

#include<iostream>
#include<algorithm>
#include<queue>
#include<deque>
#include<utility>

using namespace std;

struct Direction {
    int time;
    char dir;
};

int N,K,L,board[101][101];
int dx[4] = {0 ,1 , 0 , -1};
int dy[4] = {1 ,0 , -1 , 0};
deque<pair<int,int>> s_q;
int curDir = 0;

queue<Direction> q;


int simulate()
{
    int time=0;
    s_q.push_front({0,0});
    board[0][0] = 1;

    while(true)
    {
        time++;
        int nx = s_q.front().first + dx[curDir];
        int ny = s_q.front().second+ dy[curDir];

        if(nx < 0 || ny < 0 || nx>= N || ny >= N || board[nx][ny] ==1)return time;
        
        if(board[nx][ny] ==2)
        {
            board[nx][ny] = 1;
            s_q.push_front({nx,ny});
        }
        else
        {
            board[nx][ny] = 1;
            s_q.push_front({nx,ny});
            board[s_q.back().first][s_q.back().second] = 0;
            s_q.pop_back();

        }

        if(!q.empty() && q.front().time == time)
        {
            if(q.front().dir == 'L')curDir = (curDir+3) % 4;
            else if(q.front().dir == 'D')curDir = (curDir+1) % 4;
            q.pop();
        }
    }

}

int main(void)
{
    cin.tie(0);
    cin >> N >> K;
    for(int a=0;a<K;a++)
    {
        int x,y;
        cin >> x >> y;
        board[x-1][y-1] = 2;
    }
    cin >> L;
    for(int a=0;a<L;a++)
    {
        int time;
        char dir;

        cin >> time >> dir;
        q.push({time,dir});
    }

    cout << simulate();

    return 0;