[BOJ/C++] 백준 3190 - 뱀

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

3190번: 뱀

문제 해설

단순 구현 문제이고, 처리해야하는 예외가 많아 시뮬레이션 해보고 구현해야하는 문제였다.

주의해야할 문제의 조건은 아래와 같다.

1. 뱀의 머리가 먼저 이동한 후, 그 위치의 사과의 유무에 따라 꼬리의 이동 유무가 결정된다. 이 순서에 맞게 구현해야 한다.
2. 방향을 전환할 때, 현재 뱀의 머리의 방향을 기준으로 왼쪽, 오른쪽 방향으로 전환한다.
3. 뱀의 꼬리는 뱀의 머리가 지나간 위치로만 이동할 수 있다. 따라서 뱀의 꼬리는, 머리가 방향을 전환한 위치를 기억하고 그 위치에 나중에 도착했을 때 동일한 방향으로 전환할 수 있어야 한다.
4. 사과는 뱀이 지나가고 나면 사라진다.
5. 뱀의 머리가 벽이나 자신의 몸에 부딪히기 직전의 시간을 구한 후, 그 시간에 1을 더한 것이 게임이 끝난 시간이 된다.

코드 설명

뱀의 머리, 꼬리의 좌표와 다음에 이동해야 할 방향을 구조체로 선언하였다.

board의 숫자에 따라 상태를 표현하였는데, 각 숫자에 따른 의미는 다음과 같다.

• board[y][x] = 0 : 빈 칸
• board[y][x] = 1 : 사과가 있는 칸
• board[y][x] = 2 : 뱀의 머리, 꼬리를 포함한 몸통이 현재 위치한 칸
• board[y][x] = 3 : 뱀의 몸통이 현재 위치해있으며, 뱀의 머리가 왼쪽으로 방향을 전환하였던 칸
• board[y][x] = 4 : 뱀의 몸통이 현재 위치해있으며, 뱀의 머리가 오른쪽으로 방향을 전환하였던 칸

방향을 전환하였던 칸을 3, 4라는 숫자로 기록한 이유는, 위에서 언급한 처리해야 할 예외 3번을 처리하기 위함이다. 꼬리가 이 위치를 인식한 후 방향을 올바르게 전환해 지나가고 나면 빈 칸으로 세팅되기 때문에, 나중에 문제의 해결에 차질이 생길 일은 없다. 사과도 마찬가지로 뱀의 꼬리까지 지나가고 나면 빈 칸이 되도록 설계하였다.

또한, change[i] 배열을 통해 i시간에 뱀이 방향을 전환하였는 지 아닌 지, 전환하였다면 어느 방향으로 전환하였는 지 기록하였다. rotate함수에서는 dy, dx를 시계방향으로 방향을 기입하였음을 토대로 'L', 'D'에 따라 다음 방향을 설정해주었고, 머리가 방향을 바꾸었다면 어느 방향으로 바꾸었는지 board[head.y][head.x]에 기록해주었다.

코드

#include <iostream>
#include <cstring>
#include <vector>
using namespace std; 

// 오른쪽부터 시계 방향
int dy[4] = { 0, 1, 0, -1 }; 
int dx[4] = { 1, 0, -1, 0 }; 

int n, k;
int board[101][101]; 
char change[10001]; 

struct Head {
    int y = 1, x = 1; 
    int d = 0; 
};

struct Tail {
    int y = 1, x = 1; 
    int d = 0; 
};

bool isOut(int y, int x) {
    return y <= 0 || y > n || x <= 0 || x > n; 
}

void rotate(int& current, char direction) {
    if (direction == 'L') {
        if (current == 0) current = 3;
        else current--; 
    }
    else if (direction == 'D') {
        if (current == 3) current = 0;
        else current++;
    }
}

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

    cin >> n >> k;
    memset(board, 0, sizeof(board));
    memset(change, '#', sizeof(change));
    for (int i = 0; i < k; i++) {
        int y, x; cin >> y >> x;
        board[y][x] = 1;
    }
    int l; cin >> l;

    for (int i = 0; i < l; i++) {
        int x; char d; cin >> x >> d;
        change[x] = d;
    }

    int ret = 0;
    Head head;  Tail tail;
    board[head.y][head.x] = 2; // 뱀의 시작 위치
    while (true) {
        head.y += dy[head.d], head.x += dx[head.d];
        if (isOut(head.y, head.x) || board[head.y][head.x] == 2 || board[head.y][head.x] == 3 || board[head.y][head.x] == 4) break;
        if (board[head.y][head.x] == 1) {
            board[head.y][head.x] = 2;
        }
        else if(board[head.y][head.x] == 0){
            board[head.y][head.x] = 2;
            if (board[tail.y][tail.x] == 3) // L로 변향
                rotate(tail.d, 'L');
            else if (board[tail.y][tail.x] == 4)  // D로 변향
                rotate(tail.d, 'D');
            board[tail.y][tail.x] = 0;
            tail.y += dy[tail.d], tail.x += dx[tail.d];
        }
        ret++;
        if (change[ret] != '#') {
            rotate(head.d, change[ret]);
            if (change[ret] == 'L') board[head.y][head.x] = 3;
            else if (change[ret] == 'D') board[head.y][head.x] = 4; 
        }
    }
    cout << ret + 1<< endl;
    return 0; 
}