백준 3190 뱀

어려운 문제는 아니었으나 구현에 있어 약간 헷갈리는 부분이 있다.

자료구조 선택

1. 뱀의 움직임을 기록할 board와 사과 위치를 기록하는 apple판을 따로 두어 기록했다.
2. bfs를 할 queue와 snake의 좌표를 기록할 queue를 따로 두어 기록했다.
3. 시간과 방향을 기록할 dir_queue를 따로 두어 기록했다.

구현

1. 우선 데이터를 받아준다.
	1. 사과의 좌표가 행과 열로 주어지기 때문에 시작 좌표를 (0,0)으로 잡았다면 각 행과 열을 -1한 값을 apple 좌표에 기록해줘야 한다.
    2. 방향 정보는 queue에 기록함으로써 나중에 데이터를 받고 삭제하기 편하게끔 했다.
    
2. bfs를 돌릴 queue와 snake의 좌표를 기록할 queue에 시작좌표인 (0,0)을 넣고 board[0][0]에 뱀이 있다는 표시를 남긴다.
3. 이제 bfs를 돌리는데 queue가 빌 때까지 while문을 돌리는 식으로 하고, 시간을 1초 더해주고 시작한다.
4. 처음 방향이 오른쪽을 보고 있기 때문에 다음 좌표를 구한 뒤, 벽을 보고 있거나 뱀이 있으면 break해준다.
5. 해당 좌표에 사과가 있으면 사과 좌표를 0으로 바꿔주고, 사과가 없으면 snake의 front 값을 임시좌표에 기록하고 pop한 뒤에 board의 해당좌표값에서 뱀의 기록을 없애준다.
6. 이후 queue와 snake에 다음 좌표를 push해주고 뱀의 기록을 남긴다.
7. 마지막에 시간과 정보 입력한 것을 꺼내서 시간을 비교한 뒤에 방향을 바꿔준다.

구현 코드

#include <bits/stdc++.h>
using namespace std;

int board[101][101], apple[101][101];
int N, K, L, ans;
queue<pair<int, char>>dir_queue;

// 시작은 동쪽
int dir = 1;
// 북, 동, 남, 서 방향
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};


// 주의할 점은 확인을 하고 조건에 부합하면 pop해야 한다.
void time_check() {
    int x; char c;
    pair<int, char> cur = dir_queue.front();
    tie(x, c) = cur;
    if(x == ans) {
        if(c == 'L') {
            dir = (dir+3)%4;
        }
        else if(c == 'D') {
            dir = (dir+1)%4;
        }
        dir_queue.pop();
    }
}

void input() {
    cin >> N >> K;
    // 사과 놓기
    while(K--) {
        int x, y;
        cin >> x >> y;
        apple[x-1][y-1] = 1;
    }
    cin >> L;
    // 방향 정보 입력
    while(L--) {
        int a; char c;
        cin >> a >> c;
        dir_queue.push({a, c});
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    queue<pair<int, int>> q;
    queue<pair<int, int>> snake;
    q.push({0, 0});
    snake.push({0, 0});
    // 뱀 기록
    board[0][0] = 7;
    while(!q.empty()) {
        ans++;
        pair<int, int> cur = q.front(); q.pop();
        int x, y; tie(x, y) = cur;
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if(nx < 0 || nx >= N || ny < 0 || ny >= N || board[nx][ny] == 7) break;
        if(apple[nx][ny]) {
            apple[nx][ny] = 0;
        }
        else {
            int tx, ty;
            pair<int, int> cur = snake.front(); 
            tie(tx, ty) = cur; snake.pop();
            board[tx][ty] = 0;
        }
        q.push({nx, ny});
        snake.push({nx, ny});
        board[nx][ny] = 7;
        time_check();
    }
    cout << ans;
}