[BOJ] 3190. 뱀

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

3190번: 뱀

이 문제에서 어려운 점은 뱀이 자기 몸에 부딪혀서 게임이 끝날때를 처리해주는 부분인 것 같다.

이 부분은 몸길이와 칸에 머리가 있었던 시간을 저장한 배열을 이용하면 쉽게 구할 수 있다.

 

(현재 시간 - 몸길이)가 이동할 칸에 이전에 머리가 있었던 시간보다 작으면 몸에 부딪힌 것 이다

 

#include <iostream>
#include <vector>
using namespace std;
 
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
 
 
int n, k;
 
//사과의 좌표를 저장
bool apple[100][100];
 
//머리가 위치한 시간을 저장
int headtime[100][100];
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
 
    cin >> n >> k;
 
    //사과정보 저장
    int ax, ay;
    for (int i = 0; i < k; i++) {
        cin >> ax >> ay;
        apple[ax - 1][ay - 1] = true;
    }
 
    int l;
    cin >> l;
    int t;
    char c;
 
    //방향 회전 정보를 저장
    vector<pair<int, char>> vt;
    for (int i = 0; i < l; i++) {
        cin >> t;
        cin >> c;
        vt.push_back(make_pair(t,c));
    }
 
    int time = 0;
 
    //방향 회전정보를 이용하기 위한 인덱스
    int index = 0;
 
    //초기 방향
    int dir = 0;
 
    //초기 길이
    int len = 1;
 
    //초기 위치는 좌측 맨위쪽
    int x = 0;
    int y = 0;
    while (true) {
        //먼저 시간증가, 길이 증가, 머리 앞칸으로 이동
        time++;
        len += 1;
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        
        //벽에 부딪힘
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) break;
 
        //몸에 부딪힘 ((현재 시간 - 몸길이)가 이동할 칸에 머리가 있었던 시간보다 작으면 몸에 부딪힌 것 이다)
        if (headtime[nx][ny] != 0 && ((time - len) < headtime[nx][ny])) break;
 
        //이동한 칸에 현재 시간을 저장
        headtime[nx][ny] = time;
 
        //사과가 있는지 검사
        if (apple[nx][ny]) {
            apple[nx][ny] = false;
        }
        else {
            len -= 1;
        }
 
 
        //l번만큼 방향이동을 한다.
        if (index < l) {
            //현재시간이 방향을 회전해야하는 시간이다
            if (time == vt[index].first) {
                if (vt[index].second == 'D') {
                    dir = (dir + 1) % 4;
                }
                else if (vt[index].second == 'L') {
                    dir = (dir + 3) % 4;
                }
 
                //방향 전환했으면 index증가 (다음 방향 정보를 이용하기 위해)
                index++;
            }
        }
        
        //현재 좌표를 머리가 이동한 칸의 좌표로 변경
        x = nx;
        y = ny;
    }
 
 
 
    cout << time << '\n';
 
    return 0;
}