[boj] 백준 3190 뱀 - 시뮬레이션

[문제]

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

3190번: 뱀

 

[풀이]

시뮬레이션 문제로 주어진 조건을 잘 구현해내면 된다. 앞서 풀었던 로봇청소기와 같이 방향을 다루기 때문에 dx, dy 배열을 미리 선언해 놓고 사용하는 것이 좋다. 

push와 pop을 front, back 모두에서 할 수 있는 자료구조인 deque을 이용해 뱀의 머리와 꼬리 위치를 저장해두는 것이 키포인트다. visited 배열을 이용해 뱀이 현재 좌표에 위치해 있는지 표시해줬다. 주의할 점은 사과가 있는 2번째 조건에서 사과를 먹은 경우 해당 위치의 map을 0으로 바꿔줌으로써 사과를 먹은 처리를 해줘야 한다. 그렇지 않으면 아래 입력에서 반례가 존재한다.

입력: 5 2 2 5 2 4 6 4 D 5 D 6 D 7 D 8 D 9 D 출력: 10 정답: 14

 

[코드]

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace::std;

int n, k;
int map[101][101];
bool visited[101][101];

//오 왼 아래 위
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int turn_dir(int d, char c){
    if(c=='L'){ //왼쪽으로 90도 회전
        if(d==0) return 3;
        else if(d==1) return 2;
        else if(d==2) return 0;
        else return 1;
    }
    else if(c=='D'){ //오른쪽으로 90도 회전
        if(d==0) return 2;
        else if(d==1) return 3;
        else if(d==2) return 1;
        else return 0;
    }
}

int main() {
    cin >> n >> k;
    for(int i=0; i<k; i++){
        int r, c;
        cin >> r >> c;
        map[r-1][c-1] = 1; //사과 있음.
    }

    int l; //뱀의 방향 전환 횟수
    cin >> l;
    //x초가 끝난 후 L 왼쪽 또는 D 오른쪽으로 90도 회전
    deque<pair<int, char>> v;
    for(int i=0; i<l; i++){
        int x; char c;
        cin >> x >> c;
        v.push_back({x, c});
    }

    deque<pair<int, int>> deq;
    int x = 0, y = 0, d = 0;
    deq.push_back({x, y});
    visited[x][y] = true; //뱀이 방문
    int answer = 0;

    //d=0 오른쪽 d=1 왼쪽 d=2 아래쪽 d=3 위쪽
    while(true){
        int nx = x + dx[d];
        int ny = y + dy[d];
        answer++;

        if(nx<0 || ny<0 || nx>=n || ny>=n || visited[nx][ny]) //벽 또는 자기 자신의 몸과 부딪히면 종료
            break;
        else if(map[nx][ny]==0) { //사과가 없는 경우 꼬리를 비움
            visited[deq.back().first][deq.back().second] = false; //꼬리 비움
            deq.pop_back(); //꼬리 비움
            deq.push_front({nx, ny}); //뱀 머리 이동
            visited[nx][ny] = true;
        }
        else { //사과가 있는 경우 사과 없어지고 머리만 이동
            map[nx][ny] = 0; //사과 먹음
            visited[nx][ny] = true;
            deq.push_front({nx, ny});
        }

        if(!v.empty()){
            if(answer==v.front().first){
                d = turn_dir(d, v.front().second);
                v.pop_front();
            }
        }

        x = nx;
        y = ny;

    }

    cout << answer;

}