BOJ 3190 뱀

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

3190번: 뱀

 

문제 해결전략

이 문제를 해결하기 위한 핵심은 뱀의 꼬리 좌표와 머리 좌표를 추적하는(?) 것이라고 생각한다.

뱀이 이동할 것인지 또는 사과를 먹을 것인지 검사하기 위한 좌표 변수 ny, nx를 선언하였다. 

또한, 뱀의 좌표를 저장할 공간인 큐를 선언하였다.

큐의 구조는 뱀의 꼬리, 몸통, 뱀의 머리 식으로 구성되어 있다.

ny, nx를 이용하여 뱀의 일부분(1)인지 빈 공간(0)인지 사과(2)인지 검사한다.

만약 map[ny][nx]가 뱀의 일부분(1)이면 정지시킨다.

빈 공간(0)이면 큐의 가장 맨 앞부분(꼬리==front)을 POP 한 후, 해당 부분의 좌표 map[q.front.first][q.front.second]를 0으로 설정한다.

사과(2)이면 뱀의 머리 부분만 증가되므로 ny, nx 좌표를 큐에 PUSH한다.

 

정리하자면, 뱀의 꼬리와 머리 좌표를 추적하기 위해 큐와 좌표 변수(ny, nx)를 활용하였다.

큐는 뱀의 좌표들을 저장하는 공간이고, ny, nx 변수는 큐에게 꼬리와 머리 부분의 좌표를 받거나(POP) 또는 넣는다(PUSH).

 

 

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
#define endl "\n"
#define MAX 101
const int dy[4] = {0, 1, 0, -1};
const int dx[4] = {1, 0, -1, 0};
queue<pair<int, int>> q;
int map[MAX][MAX];
int n, k, l;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k;
    for(int i = 0; i < k; i++){
        int a, b;
        cin >> a >> b;
        map[a][b] = 2; // 사과
    }
    cin >> l;
    int t[MAX];
    char c[MAX];
    for(int i = 1; i <= l; i++){
        cin >> t[i] >> c[i];
    }
    int idx = 1, sec = 1, dir = 0;
    int ny = 1, nx = 1;
    q.push({ny, nx});
    map[ny][nx] = 1;
    ny = dy[dir] + q.back().first;
    nx = dx[dir] + q.back().second;
    while(1){
        if(ny > n || ny < 1 || nx > n || nx < 1 || map[ny][nx] == 1){ // 종료 조
            break;
        }else{
            if(map[ny][nx] == 0){ // 사과가 없을 때
                int tempY = q.front().first, tempX = q.front().second;
                q.pop();
                map[tempY][tempX] = 0;
                map[ny][nx] = 1;
                q.push({ny, nx});
            }else if(map[ny][nx] == 2){ // 사과가 있을 때
                q.push({ny, nx});
                map[ny][nx] = 1;
            }
        }
        ny += dy[dir]; nx += dx[dir];
        sec++; // 1초 증가
        // 방향 전환
        if(sec == t[idx]){ // 
            if(c[idx] == 'D'){
                dir = (dir + 1) % 4;
            }else if(c[idx] == 'L'){
                dir = (dir + 3) % 4;
            }
            idx++;
        }
    }
    cout << sec << endl;
}