백준 3190

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

 

풀이

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

다음 순서에 맞게 구현하면 된다.

뱀 전체 칸을 따로 관리하지 않고, Queue에 들어가는 값이 머리, 외부 변수에 꼬리를 저장하고 머리가 움직이는 방향 그대로 꼬리가 움직이도록 dirb 배열에 머리가 움직이는 방향을 넣어줬다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
// 1행 1열이 기준!!!!!!
// L은 왼쪽으로 회전, D는 오른쪽으로 회전
// 오 아 왼 위
int N, K, L, board[101][101], dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0}, dirb[101][101], vis[101][101];
char dir_change[10001];

int main(){
    cin>>N>>K;
    for (int i=0; i<K; i++) {
        int x, y; cin>>x>>y;
        board[x][y] = 1;
        // apple
    }
    cin>>L;
    for (int i=0; i<L; i++) {
        int X; char C;
        cin>>X; cin>>C;
        dir_change[X] = C;
    }
    // 뱀은 처음에 오른쪽을 향한다.

    queue<pair<int,int> >q;
    q.push(make_pair(1, 1));
    vis[1][1] = 1;
    int sec = 0, dir = 0, tx=1, ty = 1;
    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        sec += 1;
        // 머리를 다음칸에 위치시킴
        dirb[cur.first][cur.second] = dir;
        int nx = cur.first + dx[dir];
        int ny = cur.second + dy[dir];


        // 벽이나 자기 자신한테 닿았을 경우
        if (nx > N || nx <= 0 || ny > N || ny <= 0 || vis[nx][ny]) break;

        // 이동한 칸에 사과 체크
        if (!board[nx][ny]){
            // 없을 경우 꼬리를 이동.
            vis[tx][ty] = 0;
            int dir_s = dirb[tx][ty];
            tx += dx[dir_s];
            ty += dy[dir_s];
        }else {
            // 있을경우
            board[nx][ny] = 0;
        }

        if (dir_change[sec] == 'D') dir = (dir+1)%4;
        if (dir_change[sec] == 'L') {
            dir -= 1;
            if (dir == -1) dir += 4;
        }

        vis[nx][ny] = 1;
        q.push(make_pair(nx, ny));
    }
    cout<<sec;

}