[백준 3190] 뱀, C++

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

3190번: 뱀

본 문제는 'Dummy'라는 도스 게임이 있다. 이 게임에는 뱀이 나와서 기어 다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어 다니다가 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝난다. 좀 더 자세한 설명은 링크를 참고하길 바란다.

뱀을 머리와 꼬리를 진짜로 움직이기는 까다롭다. 그래서 뱀을 이동한 시간과 뱀의 길이를 이용하여 문제를 해결할 수 있다.

1. 방문한 칸에 사과가 있으면 뱀의 길이 증가
2. 방문한 칸이 처음일 경우 이동
3. 방문한 칸이 처음이 아닌데 시간의 차이가 뱀의 길이보다 클 경우 이동
4. 아닐 경우 종료
5. 뱀이 경지장 밖으로 나갈 경우 종료

#include <cstdio>
#include <queue>
#include <tuple>
 
using namespace std;
 
int map[101][101] = {0};
int apple[101][101];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
 
char turn[101];
int main() {
    int n, m, l, baam = 1;
 
    // 보드 크기
    scanf("%d", &n);
 
    // 사과 개수 및 위치
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        
        // 위치가 (1, 1) 시작이므로 사과 위치 조정
        x -= 1;
        y -= 1;
        apple[x][y] = 1;
    }
 
    // 방향 전환
    scanf("%d", &l);
 
    for (int i = 0; i < l; i++) {
        int t;
        char how;
        scanf("%d %c", &t, &how);
        turn[t] = how;
    }
 
    queue<tuple<int, int, int, int>> q;
    q.push(make_tuple(0, 0, 0, 0));
    map[0][0] = 0;
 
    while (!q.empty()) {
        int x, y, k, cnt;
        tie(x, y, k, cnt) = q.front();
        q.pop();
 
//        printf("====================\n");
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                printf("%d ", map[i][j]);
//            }
//            printf("\n");
//        }
 
        // 왼쪽으로 90도 회전
        if (turn[cnt] == 'L') {
            k -= 1;
            if (k < 0) k = 3;
        }
        
        // 오른쪽으로 90도 회전
        if (turn[cnt] == 'D') {
            k += 1;
            if (k > 3) k = 0;
        }
 
        int nx = x + dx[k];
        int ny = y + dy[k];
        cnt += 1;
 
        // 경지장 밖일 경우
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
            printf("%d\n", cnt);
            return 0;
        }
        else {
            // 사과일 경우
            if (apple[nx][ny] == 1) {
                baam += 1;
                apple[nx][ny] = 0;
            }
            
            // 처음 방문
            if (map[nx][ny] == 0) {
                map[nx][ny] = cnt;
                q.push(make_tuple(nx, ny, k, cnt));
            }
            else {
                
                // 뱀의 길이가 시간 차 보다 길거나 같을 경우
                if (cnt - map[nx][ny] <= baam) {
                    printf("%d\n", cnt);
                    return 0;
                }
                else {
                    map[nx][ny] = cnt;
                    q.push(make_tuple(nx, ny, k, cnt));
                }
            }
        }
    }
}