뱀 (feat. 백준, 3190번)

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

3190번: 뱀

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, K, L, dx[4]{0, 0, 1, -1}, dy[4]{1, -1, 0, 0}, arr[101][101];
    queue<pair<int, char>> q;
    deque<pair<int, int>> ans;  // 뱀의 위치 (몸 전체)
    cin >> N;
    for(register int i = 1, j; i <= N; ++i)
        for(j = 1; j <= N; ++j)
            arr[i][j] = 0;
    cin >> K;
    for(register int k = 0, x, y; k < K; ++k)
        cin >> x >> y, arr[x][y] = 1;
    cin >> L;
    char c;
    for(register int l = 0, x; l < L; ++l){
        cin >> x >> c, q.push(make_pair(x, c));
    }
    int time = 0;
    register int x = 1, y = 1, d = 0;       // (1,1) 동쪽으로 시작
    arr[x][y] = 2;
    ans.push_back(make_pair(x, y));
    while(++time){
        register int nx = x + dx[d], ny = y + dy[d];
        if(nx < 1 || nx > N || ny < 1 || ny > N)    // 벽을 만나면 종료
            break;
        if(arr[nx][ny] == 2)    // 뱀의 몸이면 종료
            break;
        ans.push_back(make_pair(nx, ny));
        if(arr[nx][ny] != 1)    // 사과가 없으면 꼬리 삭제
            arr[ans.front().first][ans.front().second] = 0, ans.pop_front();
        if(!q.empty() && q.front().first == time){ // 방향 전환할 시간이면
            if(d == 0){      // 현재 동쪽이면
                if(q.front().second == 'L')     d = 3;      // 왼쪽은 북쪽
                else    d = 2;  // 오른쪽은 남쪽
            }
            else if(d == 1){    // 현재가 서쪽이면
                if(q.front().second == 'L')     d = 2;      // 왼쪽은 남쪽
                else    d = 3;  // 오른쪽은 북쪽
            }
            else if(d == 2){    // 현재가 남쪽이면
                if(q.front().second == 'L')     d = 0;      // 왼쪽은 동쪽
                else    d = 1;  // 오른쪽은 서쪽
            }
            else{       // 현재가 북쪽이면
                if(q.front().second == 'L')     d = 1;      // 왼쪽은 서쪽
                else    d = 0;  // 오른쪽은 동쪽
            }
            q.pop();
        }
        x = nx, y = ny;
        arr[x][y] = 2;  // 뱀 머리부분 표시
    }
    cout << time;
    return 0;
}
// *&)*@*

 

1. 문제의 요구사항대로 시뮬레이션을 구현하면 되는 문제입니다.
2. 단, 뱀의 머리와 꼬리를 넣고 뺄수 있어야 하므로 저의 경우 양방향 접근이 가능한 (선입선출, 선입후출 모두 가능한) 덱(deque)을 사용하였습니다. 양방향 리스트 구조를 사용하여도 무방합니다.