3190번-뱀

문제

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

3190번: 뱀

---

접근방법

1) 접근 사고

문제의 조건을 보면 단순 구현 문제란걸 알 수 있었다.

2) 시간 복잡도

n의 범위가 작아서 완전탐색이 가능하다

3) 배운 점

구현에 초점이 맞춰져 있는 문제이다. 61번줄 부터의 인덱스 계산을 효율적으로 계산하는 코드를 배웠다. 자세한 풀이는 코드 참조

4) PS

삼성문제를 갈아먹고 씹어먹어 주겠다.

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
#define apple 2300
 
using namespace std;
 
const int MAX = 101;
int board[MAX][MAX];
queue<pair<int, char>> move_q;
int n, k, l;
int moveY[] = { 0, -1, 0, 1 };
int moveX[] = { 1, 0, -1, 0 };
 
int main(void)
{
    fastio;
    cin >> n >> k;
 
    auto search = [&]() -> int
    {
        board[0][0] = 1;
 
        int dirnum = 0;
        pair<int, int> head = { 0, 0 };
        queue<pair<int, int>> snakeState;
        snakeState.push({ 0, 0 });
 
        int cnt = 0;
        while (1)
        {
            cnt++;
            int nextY = head.first + moveY[dirnum];
            int nextX = head.second + moveX[dirnum];
 
            if (!(nextY >= 0 && nextY < n && nextX >= 0 && nextX < n)) //범위초과시 종료
                return cnt;
            else if (board[nextY][nextX] == 1) //자신의 몸통에 닿은 경우 종료
                return cnt;
            else if (board[nextY][nextX] != apple)
            {
                board[snakeState.front().first][snakeState.front().second] = 0; //1.꼬리를 짧게 만들기 위해 현재를 없애주고
                snakeState.pop();
            }
            head.first = nextY; //2.머리값 갱신. 위에서 사과가 아닌 경우에는 짧아진 만큼 앞으로 가고, 사과인 경우에는 한 칸 더 길어진다.
            head.second = nextX;
            snakeState.push(head);
            board[nextY][nextX] = 1;
 
            if (!move_q.empty())//방향 변환이 가능하다면
            {
                if (cnt == move_q.front().first)//이동 숫자가 방향 변환 차례라면
                {
                    auto curMove = move_q.front();
                    move_q.pop();
                    if (curMove.second == 'D') //동,북,서,남 순으로 인덱스 계산시 코드 단축 가능
                        dirnum = (dirnum + 3) % 4;
                    else if (curMove.second == 'L')
                        dirnum = (dirnum + 1) % 4;
                }
            }
        }
    };
 
    for (int i = 0; i < k; i++)
    {
        int y, x;
        cin >> y >> x;
        y--, x--;
        board[y][x] = apple;
    }
    cin >> l;
 
    for (int i = 0; i < l; i++)
    {
        int time;
        char dir;
        cin >> time >> dir;
        move_q.push({ time, dir });
    }
 
    cout << search() << "\n";
}