백준 3190번: 뱀 (C++)

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

문제에 적힌 절차 그대로 구현해주면 된다.

중요한 포인트는, 매회 이동을 할 때, 몸길이를 늘려서 다음 칸을 확인한다는 것이다.

늘린 이후에, 사과라면 몸길이 유지, 사과가 아니라면 몸길이 감소 순서이다.

게임 시작 시간으로부터 X초가 끝난 뒤에라고 문제에서 명시된 것처럼, 초가 끝난 이후에, 방향을 바꿔준다.

가령 3초에 뱀이 회전해야 한다면, 2~3초의 이동이 끝난 이후에 방향을 바꿔주면 된다.

머리의 이동은 어렵지 않게 구현할 수 있다. 꼬리의 다음 위치를 파악하는 것이 중요한데, 머리의 회전과 꼬리의 회전이 동시에 일어나지 않기 때문에, 꼬리를 이동할 때 마다, 4방향 탐색을 해서 가장 생긴지 오래된 몸통을 파악한 이후에, 그 몸통을 새로운 꼬리로 갱신해주면 된다.

#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
typedef pair<int, int> pii;
int n, m[101][101], k, L, age[101][101];
 
int dr[4] = { 0,1,0,-1 };
int dc[4] = { 1,0,-1,0 };
struct Snake {
    pii head;
    pii tail;
    int dir;
};
queue<Snake> q;
 
int time = 0;
vector<pair<int, char > > turn;
 
void bfs(Snake s) {
    q.push(s);
    m[1][1] = 1;
    int ag = 0;
    age[1][1] = 1;
 
    while (!q.empty()) {
 
        Snake cur = q.front();
        q.pop();
 
        time++;
 
        int nr = cur.head.first + dr[cur.dir];
        int nc = cur.head.second + dc[cur.dir];
        if (nr <= 0 || nc <= 0 || nr > n || nc > n || m[nr][nc] == 1)
            return; //충돌 검사
 
        if (m[nr][nc] == 4) { //머리 늘려서 이동했는데 사과인 경우
            m[nr][nc] = 1;
            age[nr][nc] = 1; //나중에 꼬리 갱신할 때, 가장 오래된 몸통을 꼬리로 하기 위함
        }
        else {
            m[nr][nc] = 1;
            age[nr][nc] = 1;
            //사과 아니면 꼬리 이동
 
            pii pos;
            int maxAge = 0;
            for (int j = 0; j < 4; j++) {
 
                int tnr = cur.tail.first + dr[j];
                int tnc = cur.tail.second + dc[j];
                if (tnr <= 0 || tnc <= 0 || tnr > n || tnc > n || age[tnr][tnc] == 0) continue;
 
                if (age[tnr][tnc] > maxAge) {
                    maxAge = age[tnr][tnc];
                    pos = { tnr, tnc }; //가장 오래된 몸통
                }
            }
            m[cur.tail.first][cur.tail.second] = 0; //꼬리 제거
            age[cur.tail.first][cur.tail.second] = 0;
            cur.tail.first = pos.first; //새로운 꼬리
            cur.tail.second = pos.second;
            m[nr][nc] = 1; //다음 머리의 위치가 직전 꼬리의 위치였을 경우
            age[nr][nc] = 1;
        }
        cur.head.first = nr;
        cur.head.second = nc;
 
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (age[i][j] > 0) age[i][j]++; //전체 몸통 나이 증가
 
 
        //초 끝나고 방향 전환
        for (int i = 0; i < turn.size(); i++) {
 
            if (turn[i].first == time) {
                if (turn[i].second == 'L') {
                    cur.dir = (cur.dir + 3) % 4;
                    break;
                }//왼쪽으로 90도
                else {
                    cur.dir = (cur.dir + 1) % 4;
                    break;
                }//오른쪽 90
            }
        }
        q.push(cur);
 
    }
}
int main(void) {
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        int r, c;
        cin >> r >> c;
        m[r][c] = 4; //사과
    }
 
    cin >> L;
    for (int i = 0; i < L; i++) {
        int sec;
        char d;
        cin >> sec >> d;
        turn.push_back({ sec, d });
    }
 
    Snake snake;
    snake.head = { 1, 1 };
    snake.tail = { 1, 1 };
 
    snake.dir = 0;
    bfs(snake);
    cout << time;
    return 0;
}