BOJ 3190 - 뱀(C++)

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

3190번: 뱀

 

풀이

Queue를 이용하여 뱀의 이동에 따른 머리의 위치정보를 계속 갱신

Queue는 FIFO(First In First Out)으로 Queue의 첫부분은 꼬리에 대한 정보, Queue의 끝부분은 머리에 대한 정보를 담음

1. 뱀 머리의 새로운 위치 계산

  - 현재 뱀의 머리(Queue.back())와 방향 정보로 새로운 위치를 계산

  - 계산한 위치가 격자를 벗어나거나 뱀의 몸에 부딪히면 게임 끝(return false)

    - 뱀의 위치정보를 2차원 배열에 갱신하면서 이차원 배열에서 새로운 위치에 뱀이 있는지 없는지 확인하여 검사 

  - 새로운 위치에 사과가 없다면 2. 사과가 있다면 3.

 

2. 길이가 그대로 이므로 Queue의 길이가 유지되어야함

  - Queue에 뱀의 머리 정보가 추가되면서 뱀의 꼬리(Queue.front())가 삭제되어야함

 

3. 사과를 먹었기 때문에 길이가 1 증가함

  - Queue에 뱀의 머리 정보만 추가함

 

4. 뱀의 이동이 끝나면 현재 시간에 방향이동 지시가 있는지 체크

  - 명령어가 R이면 시계 방향 이동이므로 dir=(dir+1)%4

  - 명령어가 L이면 반시계 방향 이동이므로 dir=(4+dir-1)%4

 

#include <queue>
#include <iostream>

using namespace std;

int N;

int map[101][101];
int dy[] = {0,1,0,-1};
int dx[] = { 1,0,-1,0 };
queue<pair<int, char>> command;
queue<pair<int, int>> snake;

int change_dir(int dir, char c) {
    if (c == 'D') //명령어가 D면 시계방향 회전
        dir = (dir + 1) % 4;
    else // L이면 반시계방향 회전
        dir = (4 + dir - 1) % 4;
    return dir;
}

bool go(int dir) {
    // 뱀 머리의 다음 위치 계산
    int ny = snake.back().first + dy[dir];
    int nx = snake.back().second + dx[dir];

    // 뱀의 머리가 칸 밖으로 나가거나 몸에 부딪히면 게임 끝
    if (ny <= 0 || nx <= 0 || ny > N || nx > N || map[ny][nx] == 1)return false;

    // 뱀이 사과를 먹지않으면 뱀의 길이가 유지되어야함
    // 꼬리의 위치도 이동을 현재 꼬리의 위치정보를 지우고 queue의 2번째 위치 정보가 꼬리가 됨
    if (map[ny][nx] != -1) {
        map[snake.front().first][snake.front().second] = 0;
        snake.pop();
    }
    // 사과를 먹든 안먹든 뱀의 새로운 머리 정보는 갱신
    map[ny][nx] = 1;
    snake.push(make_pair(ny, nx));

    return true;
}

int main() {
    int K;
    cin >> N >> K;
    int y, x;
    for (int i = 0; i < K; i++) {
        cin >> y >> x;
        map[y][x] = -1;
    }

    cin >> K;
    int time;
    char c;
    for (int i = 0; i < K; i++) {
        cin >> time >> c;
        command.push(make_pair(time, c));
    }

    snake.push(make_pair(1, 1));
    map[1][1] = 1;
    time = 0;
    int dir = 0;
    while (1) {
        time++;
        if (!go(dir))break;
        // 이동이 끝나면 방향 이동 지시가 있는지 확인
        if (command.size()>0 && time == command.front().first) {
            dir = change_dir(dir, command.front().second);
            command.pop();
        }
    }

    cout << time;
    return 0;
}