[ 백준 ] 3190 / 뱀

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
102/228
post-thumbnail

# Appreciation

/*
 * Problem :: 3190 / 뱀
 *
 * Kind :: Simulation
 *
 * Insight
 * - 뱀의 꼬리와 머리를 Deque 의 back 과 front 에 대응시켜 생각할 수 있다
 *   # 즉, Deque<Point> 에서 맨 앞의 좌표는 현재 뱀의 머리가 있는 좌표,
 *     맨 뒤의 좌표는 현재 뱀의 꼬릭가 있는 좌표이다
 *
 * - 뱀의 방향 전환 정보는 Queue 를 이용해서 다룰 수 있다
 *   # 정해진 시간이 되면 방향 전환 정보를 꺼내서 사용한 후 pop 시키는 형태로 구현했다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

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

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N;
int board[100][100];
enum Status { EMPTY, APPLE, BODY };
int dy[4] = {+1, 0, 0, -1};
int dx[4] = {0, +1, -1, 0};
enum Direction { SOUTH, EAST, WEST, NORTH };
struct Info { int X; char C; };
struct Point { int y, x; };
struct Snake { int dir; deque<Point> body; };

// Set up : Functions Declaration
bool isValid(int y, int x);
bool move(Snake &snake);
void updateDir(Snake &snake, queue<Info> &infos, int time);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int K;
    cin >> N >> K;
    for (int i=0; i<K; i++) {
        int r, c;
        cin >> r >> c;
        /* 맨 위 맨 좌측 좌표 - 문제 (1,1) => 코드 (0,0) */
        board[r-1][c-1] = APPLE;
    }
    int L; cin >> L;
    queue<Info> infos;
    for (int i=0; i<L; i++) {
        int X; char C;
        cin >> X >> C;
        infos.push({X, C});
    }

    // Process
    deque<Point> body;
    body.push_back({0, 0});
    Snake snake{EAST, body}; /* 뱀 초기화 */

    int time = 0;
    /* 뱀이 움직일 수 있다면 */
    while (move(snake)) {
        /* 게임시간 1초 증가 */
        time++;
        /* 게임시간에 따라 뱀의 방향 업데이트 */
        updateDir(snake, infos, time);
    } time++; /* 실패하는데도 1초의 시간이 필요함 */

    // Control : Output
    cout << time << endl;
}

// Helper Functions
bool isValid(int y, int x)
/* 주어진 좌표가 유효하면 true 를 반환, 그 외 false 를 반환 */
{
    return y >= 0 && y < N && x >= 0 && x < N;
}

bool move(Snake &snake)
/* 뱀이 움직일 수 있으면 true 를 반환, 그 외 false 를 반환 */
{
    int dir = snake.dir;
    Point head = snake.body.front(); /* Deque 의 맨 앞 좌표는 뱀의 머리를 가리킴 */
    Point tail = snake.body.back();  /* Deque 의 맨 뒤 좌표는 뱀의 꼬리를 가리킴 */

    int nhy = head.y + dy[dir]; /* new head y */
    int nhx = head.x + dx[dir]; /* new head x */

    /* 새로운 뱀머리의 좌표가 유효하지 않은 좌표이거나 자기 몸통이면 움직이는데 실패 */
    if (not(isValid(nhy, nhx)) || board[nhy][nhx] == BODY) {
        return false;
    }

    /* 새로운 뱀머리의 좌표에 사과가 없으면 */
    if (board[nhy][nhx] != APPLE) {
        /* 꼬리를 줄여줌 */
        board[tail.y][tail.x] = EMPTY;
        snake.body.pop_back();
    }
    /* 새로운 뱀머리의 좌표에 사과가 있든 없든 뱀머리는 늘려줌 */
    board[nhy][nhx] = BODY;
    snake.body.push_front({nhy, nhx});

    return true;
}

void updateDir(Snake &snake, queue<Info> &infos, int time)
/* 게임시간에 따라 뱀의 방향을 전환시켜줌 */
{
    if (infos.empty()) return;
    Info info = infos.front();
    if (info.X == time) {
        infos.pop();
        /* 사실 아부분을 2차원 전역 배열로 미리 선언해놓고 쓰면 더 좋음 */
        if (info.C == 'L') {
            switch (snake.dir) {
                case SOUTH: snake.dir = EAST;  return;
                case EAST:  snake.dir = NORTH; return;
                case WEST:  snake.dir = SOUTH; return;
                case NORTH: snake.dir = WEST;  return;
                default: throw;
            }
        }
        if (info.C == 'D') {
            switch (snake.dir) {
                case SOUTH: snake.dir = WEST;  return;
                case EAST:  snake.dir = SOUTH; return;
                case WEST:  snake.dir = NORTH; return;
                case NORTH: snake.dir = EAST;  return;
                default: throw;
            }
        }
    }
}
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글