[C++] 백준 3190 뱀 - 특정 좌표를 기억하기 위한 큐 및 배열 사용하기

문제

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

 

리뷰

문제 유형: 구현, 시뮬레이션, 자료구조

 

격자 위에서 그래프 탐색 방식과 비슷하게 x, y 축 이동 방향을 회전시키면서 이동하다가, 사과를 발견하면 몸통의 길이를 늘려주고, 범위 밖으로 나가거나 혹은 자기자신과 부딪히면 종료되도록 만들어야 한다.

이 때 필요한 시퀀스를 정리해볼 필요가 있다.

• 입력값에 따라 이동 방향을 회전 시키기 → dir[4][2] 의 반복
• 아이템을 먹었을 경우 늘어나는 몸통 좌표 기억하기 / 먹지 않았을 경우 줄어드는 꼬리 부분
  → 뱀의 몸통 좌표들을 기억하는 큐:머리가 back, 꼬리가 front가 되어 pop and push로 구현할 수 있다.
• 범위를 나가거나 → InRange 함수로 구현 가능
• 자기 자신과 부딪히거나 → 몸통을 저장하는 큐(벡터로 구현한다면 전체 search로 구현할 수는 있다)
  → 또는 맵 위에다가 뱀의 몸통이라고 표시해두는 방식으로 구현할 수 있다

 

큐를 이용해서 꼬리 부분을 pop하여 뱀 전체가 이동했다고 구현할 수 있다는 것을 빠르게 파악하지 못했고,
맵에 자체적으로 뱀의 위치를 기록해둠으로써 전체 서치에 대한 시간 복잡도를 줄일 수 있음을 알게되었다.
(벡터 전체 서치 후 erase를 진행해도 제한시간을 넘지는 않는다)

 

전체 반복을 진행하면서 '순서'를 헷갈리지 않도록 유의해야 한다(언제 몸통이 늘어나는지, 언제 방향이 바뀌고 움직이는지. '초'가 지난 후 해당 방향으로 회전한다고 하였으므로, while 반복이 다시 시작되기 전에 방향이 이미 바뀌어있어야 한다.)

 

코드

본인의 방식으로 작성된 코드이므로, 효율적이지 않다(전체 서치 진행)는 것을 감안해야 한다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N, K, L;
int map[101][101];
vector<int> apple(101);
queue<pair<int, char>> move_info;

bool InRange(int x, int y){
    return (x<1 || x>N || y<1 || y>N) ? false:true;
}

bool Body(int x, int y, vector<pair<int, int>>& body){
    for(auto iter=body.begin(); iter!=body.end(); iter++){
        if(x == iter->first && y == iter->second)
            return true;
    }
    return false;
}

int Solve(){
    int answer = 0;
    cin >> N >> K;
    fill(&map[1][1], &map[N][N+1], 0);
    for(int k=0; k<K; k++){
        int x, y;
        cin >> x >> y;
        map[x][y] = 1;
    }
    cin >> L;
    for(int l=0; l<L; l++){
        int x;  char y;
        cin >> x >> y;
        move_info.push({x, y});
    }

    vector<pair<int, int>> body;
    body.push_back({1, 1});
    //map[0][0] = 1;
    int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int dir_value = 0;
    
    while(true){
        int mtime = move_info.front().first;
        char direction = move_info.front().second;
        int cx = body.back().first;
        int cy = body.back().second;

        //cout << "cx, cy: " << cx << ", " << cy;
        //cout << "dir value: " << dir_value;
        int nx = cx + dir[dir_value][0];
        int ny = cy + dir[dir_value][1];
        //cout << " nx, ny: " << nx << ", " << ny <<'\n';
        if(!InRange(nx, ny) || Body(nx, ny, body)){
            //cout << "break!";
            break;
        }

        body.push_back({nx, ny});

        if(map[nx][ny] != 1)
            body.erase(body.begin());
        else{
            map[nx][ny] = 0;
            //cout << "apple! " << '\n';
        }

        answer ++;

        if(answer == mtime){
            move_info.pop();
            if(direction == 'D')    dir_value = (dir_value+1)%4;
            else{
                dir_value -= 1;
                if(dir_value < 0)
                    dir_value = 3;
            }
        }
    }

    return answer+1;
}

int main(){
    int answer = Solve();
    cout << answer;
    return 0;
}

 

 

비슷한 문제

백준 16235 나무 재테크: https://www.acmicpc.net/problem/16235