[삼성SW테스트] 백준 3190번 - 뱀 (정답률 32%)

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

3190번: 뱀

삼성 SW테스트 기출 문제다. (유형: 시뮬레이션)

뱀의 머리와 꼬리에 대한 조작이 필요한 시뮬레이션 문제다. 이렇게 양 방향으로 입력/삭제가 필요할 때는 'deque'자료구조가 용이하다.

 

나는 뱀의 몸(머리/꼬리포함)이 놓여있는 위치를 저장하기 위해 deque<pair<int, int> > snake를 사용하였고, 

방향 전환에 대한 조작을 위해 queue<pair<int, char> > turn 를 선언했다.

 

또, 사과가 놓여있는 장소와 몸이 놓여있는 여부를 표시하기 위해 vector<vector<bool> > check, apple을 선언했다.

 

주어진 문제의 순서에 맞게 그대로 정확하게 구현하는 것이 중요했다.

그리고 정말 중요한 것은, 방향 전환에 대한 큐에 저장된 가장 마지막의 시간보다 더 늦게 끝날 경우를 대비해 처리해주는 것이었다. ( 60번째 줄의 turn.size() ).

 

아래는 전체 소스코드. (0ms)

#include <iostream>
#include <deque>
#include <queue>
#include <vector>
#define MAX 101
using namespace std;
 
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; // 동, 남, 서, 북
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    vector<vector<bool> > check, apple;
    deque<pair<int, int> > snake;
    queue<pair<int, char> > turn;
    int N, K;
    cin >> N >> K;
    check.assign(MAX, vector<bool>(MAX, false)); // 뱀의 몸이 놓여있는 공간.
    apple.assign(MAX, vector<bool>(MAX, false)); // 사과의 위치
    for (int k = 0; k < K; k++){
        int a_r, a_c;
        cin >> a_r >> a_c;
        apple[a_r][a_c] = true;
    }
    int L;
    cin >> L;
    for (int l = 0; l < L; l++){
        int when;
        char toWhere;
        cin >> when >> toWhere;
        turn.push(make_pair(when, toWhere)); // front부터 검사.
    }
 
    int sec = 0; // 초기 시간.
    int curdir = 0; // 초기 방향. 
    check[1][1] = true; // 초기 위치 체크.
    snake.push_front(make_pair(1, 1)); // 초기 머리 위치. // 머리는 front, 꼬리는 뒤에.
    while (1){
        // 다음 시간 시작.
        sec++;
        // 다음 머리 위치 계산
        int cur_head_r = snake.front().first;
        int cur_head_c = snake.front().second;
        int nr = cur_head_r + direction[curdir].dr;
        int nc = cur_head_c + direction[curdir].dc;
        // 머리 위치에 따른 계속여부 결정
        if (nr < 1 || nc < 1 || nr > N || nc > N || check[nr][nc])
            break;
        // 계속해도 괜찮으면 다음 머리위치를 snake에 넣고, check해주자.
        snake.push_front(make_pair(nr, nc));
        check[nr][nc] = true;
        // 머리가 이동한 곳에 사과가 있으면 먹어 없애주고,
        if (apple[nr][nc])
            apple[nr][nc] = false;
        // 사과가 없으면 꼬리를 당겨오자.
        else{
            check[snake.back().first][snake.back().second] = false;
            snake.pop_back();
        }
 
        // 여전히 방향 바꿀 것이 있고, 입력해둔 시간에 도달했을 때.
        if (turn.size() && sec == turn.front().first){
            if (turn.front().second == 'D'){
                curdir = (curdir + 1) % 4;
            }
            else if (turn.front().second == 'L'){
                if (curdir == 0) curdir = 3;
                else curdir -= 1;
            }
            turn.pop();
        }
    }    
    cout << sec << '\n';
    return 0;
}