[백준/boj] 3190번 뱀 문제풀이

코테 준비는 전부터 했지만 구현 실력이 부족한 것 같아 구현 문제를 하나씩 풀어보려고 한다! 골랜디가 되는 그날까지 열심히!

문제 링크

한 번은 접해 봤을 이 게임을 구현하면 되는 문제이다. 뱀이 사과를 먹었을 때와 먹지 못했을 때를 잘 구분해서 구현해주면 된다. 뱀이 진행하면서 뱀의 머리 좌표가 새로 생기고, 뱀의 꼬리 좌표가 사라지는 구조이기 때문에 구현을 쉽게 하기 위해 deque을 사용하였다.

문제 코드는 다음과 같다.

// BOJ 3190
// Authored by mocoko

#include <bits/stdc++.h>

using namespace std;

int board[101][101];
deque<pair<int, int>> DQ;
vector<pair<int, char>> V;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int time = 0;
    int idx = 0;
    int d = 0;

    int N, K;
    cin >> N >> K;

    DQ.push_back({1, 1});
    board[1][1] = 1;

    for (int i = 0; i < K; i++)
    {
        int r, c;
        cin >> r >> c;
        board[r][c] = -1;
    }

    int L;
    cin >> L;

    for (int i = 0; i < L; i++)
    {
        int x;
        char dir;
        cin >> x >> dir;
        V.push_back({x, dir});
    }

    while (1)
    {
        auto head = DQ.front();
        int nx = head.first + dx[d];
        int ny = head.second + dy[d];

        time++;

        if (nx < 1 || nx > N || ny < 1 || ny > N || board[nx][ny] == 1)
        {
            break;
        }

        // 사과를 먹은 경우
        if (board[nx][ny] == -1)
        {
            board[nx][ny] = 1;
            DQ.push_front({nx, ny});
        }
        // 사과를 먹지 못한 경우
        else
        {
            board[nx][ny] = 1;
            board[DQ.back().first][DQ.back().second] = 0;
            DQ.push_front({nx, ny});
            DQ.pop_back();
        }

        // 방향 전환 L의 경우 (d+3)%4, D의 경우 (d+1)%4
        if (V[idx].first == time)
        {
            if (V[idx].second == 'L')
            {
                d = (d + 3) % 4;
            }
            else
            {
                d = (d + 1) % 4;
            }

            idx++;
        }
    }

    cout << time;

    return 0;
}

[이미지 출처] https://pin.it/vX4beYlgi