[삼성 기출 문제] 백준 3190 뱀

문제 링크

클릭시 이동합니다!

어떻게 풀까?

대표적인 시뮬레이션 문제입니다.

시뮬레이션에서 가장 중요한 것은 순서를 아주 잘 파악해야 한다는 것입니다.

이 문제의 경우에는 순서가 다음과 같습니다.

1. 몸길이를 늘린다.

2. 사과가 있으면 사과가 없어지고, 꼬리는 움직이지 않는다.

3. 사과가 없다면 몸길이를 줄여서 꼬리가 위치한 칸을 한 칸 비운다.

입니다. 위에 안나와 있어서 햇갈리는 부분은 바로 머리의 회전 입니다. 

입력에서 보면, 머리 회전에 관해서 X와 C가 나오는 것을 볼 수 있습니다.

그리고, X가 끝난 후에 회전하는 것을 알 수 있습니다!

죽는것은, 벽에 닿거나 뱀의 몸에 닿는 경우이죠.

즉, 모든 조건을 추가하면,

1. 몸길이를 늘린다.

2. 사과가 있으면 사과가 없어지고, 꼬리는 움직이지 않는다.

3. 사과가 없다면 몸길이를 줄여서 꼬리가 위치한 칸을 한 칸 비운다.

4. 만약, 시간초가 X초라면, 머리를 회전한다.

5. 벽이나 뱀의 몸에 닿는 경우엔 게임을 종료하고 시간을 출력한다.

우선, 뱀은 머리와 꼬리만 이동합니다.

이 때 사용해볼만한 자료구조는 덱입니다. 덱의 머리를 이동할 때에는, 덱의 맨 앞에 있는 좌표를 이동 후, 덱의 맨 앞에 넣고,

꼬리가 사라져야할 때에는 해당 위치의 값을 0으로 바꾸면서 pop을 해버리면 아주 손쉽게 뱀의 이동을 만들 수 있습니다.

또한, 뱀의 몸을 -1, 아무것도 없는 맵을 0, 사과를 1로 해서 관리하면, 맵을 편리하게 이용할 수 있습니다!

그리고, 약간 귀찮은게 뱀의 머리 회전이 오른쪽과 왼쪽으로 주어진 다는 점입니다.

이는, 순환의 특징을 이용해서 해결할 수 있습니다.

생각해보면, 오른쪽으로 머리가 회전한다면, 머리는 오른쪽->아래->왼쪽->위->오른쪽-> ... 이 반복됩니다.

왼쪽인 경우에는 이와 반대로 오른쪽->위->왼쪽->아래->오른쪽 -> ... 이라는 것을 알 수 있죠.

이 때, 오른쪽을 0, 아래를 1, 왼쪽을 2, 위를 3이라고 설정하면,

머리가 오른쪽으로 회전할 때에는 (현재 방향 + 1) %4 로 다음 방향을 나타낼 수 있습니다.

머리가 왼쪽으로 회전할 때에는 (현재 방향 - 1) %4 입니다. 하지만, 현재방향이 0인 경우, -1%4가 되어 값이 이상해집니다.

이 때에는, mod연산자의 특징을 이용해서 (현재방향 + 4 - 1) %4 로 나타낼 수 있습니다.

즉, 시간 마다 오른쪽(+1)로 이동하는지, 왼쪽(-1)로 이동하는지 배열에 담아두고,

다음 방향 = (4 + 현재 방향 - 이동방향) %4 를 이용하면 다음에 머리가 어디로 이동해야할지 쉽게 구할 수 있습니다!

코드

//https://www.acmicpc.net/problem/3190
// BOJ 3190 뱀
#pragma once
#include<iostream>
#include<deque>
 
using namespace std;
typedef pair<int, int> pii;
int comm[101][2];
int nd = 1;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
 
deque<pii> dq;
 
int map[100][100], n, k;
int conv[256];
 
int main() {
    cin >> n >> k;
    conv['L'] = -1;
    conv['D'] = 1;
 
    int r, c;
    r = c = 0;
 
    while (k--) {
        int ar, ac;
        cin >> ar >> ac;
        ar--; ac--;
 
        map[ar][ac] = 1;
    }
 
    int l;
 
    cin >> l;
 
    for (int i = 0; i < l; i++){
        int x;
        char t;
        cin >> x >> t;
        comm[i][0] = x;
        comm[i][1] = conv[t];
    }
 
    int t = 0;
 
    dq.push_back({ r,c });
    map[r][c] = -1;
 
    int tcnt = 0;
 
    while (true) {
        t++;
        pii next = dq.front();
 
        next.first += dr[nd];
        next.second += dc[nd];
 
        if (next.first < 0 || next.second < 0 || next.first >= n || next.second >= n) {
            break;
        }
        else if (map[next.first][next.second] == -1) break;
 
        else if (map[next.first][next.second] == 0) {
            pii tail = dq.back();
            map[tail.first][tail.second] = 0;
            dq.pop_back();
        }
 
        map[next.first][next.second] = -1;
        dq.push_front(next);
 
        if (comm[tcnt][0] == t) {
            nd = (4+nd + comm[tcnt++][1]) % 4;
        }
    }
    
    cout << t;
 
    return 0;
}
 

시간 복잡도

최악의 경우는 마지막에 주어진 회전까지 머리가 모두 회전한 뒤에 맵의 한 변의 길이인 N초 만큼 살아가는 경우입니다.

따라서 시간복잡도는 O(N+MAX(X)) 입니다.