[BaekJoon/백준] 3190번 뱀

 

 

문제에서 하라는 대로 해주면 되는 시뮬레이션 문제였다.

 

구현하기에 수월하다고 생각되는 방식은, deque를 이용하는 것이었다.

앞/뒤로 push,pop이 가능한 deque를 이용해서, 뱀의 좌표를 저장하며 구현했다.

 

반복문 종료 조건에는 두 가지가 있다

1. 맵을 벗어난 경우
2. 뱀의 몸통에 부딪힌 경우

 

bool VISIT을 이용해서, 현재 방문처리를 진행했고

deque<pair<int, int>>를 이용해서, 뱀이 차지하고 있는 좌표들을 저장했다.

#include <iostream>
#include <queue>
#include <deque>

// 직접 배열을 구현해서 시뮬레이션 하는 방법과, 숫자로만 계산하는 방법이 있겠다.
// => 맵을 벗어나는 처리를 해주기 위해선,, 숫자로만 계산하는 방법으론 안되겠구나..!

using namespace std;

int N, K, L, CONT;

int MAP[101][101];
bool VISIT[101][101];

// 동 남 서 북
int mx[4] = {0, 1, 0, -1};
int my[4] = {1, 0, -1, 0};

int POS_X, POS_Y; // 현재 위치
int D; // 현재 direction


queue<pair<int, char>> inf; // 방향 전환 정보
deque<pair<int, int>> snake; // 뱀 정보. back이 대가리, front가 꼬리.

int main() {
    
    int x, y;
    char z;
    
    cin >> N >> K;
    
    
    for(int i = 0; i < K; i++) {
        
        cin >> x >> y;
        
        MAP[x - 1][y - 1] = 1; // 사과
        
    }
    
    
    cin >> L;
    
    for(int i = 0; i < L; i++) {
        
        cin >> x >> z;
        
        inf.push({x, z});
    }
    
    
    VISIT[0][0] = true;
    snake.push_back({0, 0});
    
    
    while(1) {
                
        CONT++; // 시간
        
        
        POS_X += mx[D];
        POS_Y += my[D];
        
        // 맵을 벗어난 경우
        if(POS_X < 0 || POS_X >= N || POS_Y < 0 || POS_Y >= N)
            break; // 종료
        // 뱀에 몸통이 부딪힌 경우
        if(VISIT[POS_X][POS_Y])
            break; // 종료
        
        snake.push_back({POS_X, POS_Y});
        VISIT[POS_X][POS_Y] = true;
        
        if(MAP[POS_X][POS_Y] == 0) { // 사과가 아니라면
            VISIT[snake.front().first][snake.front().second] = false;
            snake.pop_front(); // 꼬리 자름.
        } else { // 사과라면
            MAP[POS_X][POS_Y] = 0; // 사과 없앰 .
        }
        
        
        if(!inf.empty() && inf.front().first == CONT) { // 방향전환시간이라면
            
            switch (inf.front().second) {
                case 'D':
                    D = (D + 1) % 4;
                    break;
                    
                default: // == case 'L'
                    D = D - 1;
                    if(D < 0)
                        D = 3;
                    break;
            }
            
            inf.pop();
        }
    }
    
    
    cout << CONT << "\n";
    
}

 

처음 제출했을 때, 틀렸습니다가 떴는데, 사과를 먹었을 때 사과를 지워주는 처리를 해주지 않아서였다!!

(https://www.acmicpc.net/board/view/81683)

 

 

소요 시간 : 30분

 

---

 

다시 한번 풀어봤다.

이전에 푼 것을 보지 않은 채로 풀어봤는데, 이전 풀이가 더 깔끔하다는 것을 느꼈다.

 

이번엔 방문처리를 set으로 했는데, 이전에 풀었을 때에는 VISIT 을 이용해서 간단하게 처리했었군..!

#include <iostream>
#include <queue>
#include <deque>
#include <set>

using namespace std;


int N, K, L;


// 시계방향 기준으로 작성했음
int mx[4] = {0, 1, 0, -1};
int my[4] = {1, 0, -1, 0};

// 맨위 맨 좌측에 위치하고, 오른쪽을 향하고, 길이는 1
int SX = 0, SY = 0; // 대가리 위치
int DIR = 0;
int LEN = 1;
int COUNT = 0;

int main() {
    
    deque<pair<int, int>> SNAKE;
    set<pair<int, int>> SNAKE_M;

    
    
    int apple_x, apple_y;
    
    cin >> N >> K;
    
    vector<vector<int>> MAP(N, vector<int>(N, 0));
    
    for(int i = 0; i < K; i++) {
        cin >> apple_x >> apple_y;
        
        MAP[apple_x - 1][apple_y - 1] = 1;
        
    }
    
    cin >> L;
    
    int t;
    char d;
    
    // FIFO니까
    queue<pair<int, char>> info;
    for(int i = 0; i < L; i++) {
    
        cin >> t >> d;
        
        info.push({t, d});
        
    }
    
    
    
    SNAKE.push_back({0, 0});
    SNAKE_M.insert({0, 0});

    
    
    
    while(1) {
        
        COUNT++;
        
        int t = info.front().first;
        int d = info.front().second;
        
        
        int xx = SX + mx[DIR];
        int yy = SY + my[DIR];
        
        
        if(xx < 0 || xx >= N || yy < 0 || yy >= N)
            break;
        
        
        SNAKE.push_front({xx, yy});
        
        if(SNAKE_M.find({xx, yy}) == SNAKE_M.end())
            SNAKE_M.insert({xx, yy});
        else
            break;


        if(MAP[xx][yy] == 1)
            MAP[xx][yy] = 0;
        else {
            SNAKE_M.erase({SNAKE.back().first, SNAKE.back().second});
            SNAKE.pop_back();
        }
        
        
        
        
        if(t == COUNT) { // 방향 전환
            
            if(d == 'D') {
                DIR = (DIR + 1) % 4;
            } else {
                DIR = DIR - 1;
                
                if(DIR < 0)
                    DIR = 3;
            }
            
            
            info.pop();
        }
        
        
        SX = xx; SY = yy;
        
    }
    
    cout << COUNT;
    
    
}

도중에 헤맸었는데, 문제에서는 1 - base 인데 나는 0 - base로 해서 생긴 문제였다.

 

소요시간 : 30분