[백준] 뱀(C++)

문제 URL

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

3190번: 뱀

 

[문제 설명]

도스게임(뱀 게임) 규착에 따라 보드의 크기, 사과의 개수와 위치, 뱀의 방향 전환 정보가 주어질 때 게임이 몇 초에 끝나는지 출력하는 문제이다. 

도스게임의 규칙

 

 

 

[문제 풀이]

문제에서 요구하는 규칙을 그대로 구현하면 되었다. (하지만 개인적으로 문제 이해 자체가 어려웠다.)

사과의 위치를 저장하기 위해서 map을, 뱀의 꼬리를 자르기 위해서 queue를 사용했다.

---

#include <iostream>
#include <vector>
#include <queue>
#define X first
#define Y second
using namespace std;

//하 상 우 좌 -> 좌측 위 기준
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

int N, K, L;
int map[100][100];
char direction[10001];
queue <pair<int, int>> q;  // 꼬리 잘라내기를 위한 큐

// 1.머리를 hx, hy로 옮김, 게임시간 cnt
// hx, hy: 현재 머리가 움직일 좌표, px, py: 머리가 존재했던 좌표
int Move(int hx, int hy, int px, int py, int cnt) {
    // 종료조건 -> 몸에 부딪히거나 벽에 박으면 종료
    if (hx < 0 || hx >= N || hy < 0 || hy >= N || map[hx][hy] == 1) {
        return cnt;
    }

    // 첫 노드는 확인하지 않음
    if (cnt != 0) {
        // 2. 해당 칸에 사과가 있는지 없는지 확인
        if (map[hx][hy] == 2) {
            // 사과가 있으면 머리를 1로 바꿈
            q.push({ hx,hy });
            map[hx][hy] = 1;

        }
        // 사과가 없으면
        else {
            q.push({ hx,hy });
            map[hx][hy] = 1;
            auto tail = q.front();
            q.pop();
            map[tail.X][tail.Y] = 0;  // 꼬리를 0으로 바꿈

        }
    }
    else {  // 첫 노드일 경우
        map[hx][hy] = 1;
    }

    // 3. 다음 머리를 옮길 위치 지정
    // 현재 방향을 구함 
    int dirX = hx - px;
    int dirY = hy - py;
    
    // 머리를 옮김 ->  머리의 방향을 바꿔야할 경우
    int nx, ny; //다음 갈 곳
    nx = 0;
    ny = 0;

    //좌측으로 머리를 꺾음
    if (direction[cnt] == 'L') {
        //현재 방향이 아래쪽
        if (dirX == dx[0] && dirY == dy[0]) {
            nx = hx;
            ny = hy + 1;
        }//현재 방향이 위쪽
        else if (dirX == dx[1] && dirY == dy[1]) {
            nx = hx;
            ny = hy - 1;
        }//현재 방향이 오른
        else if (dirX == dx[2] && dirY == dy[2]) {
            nx = hx - 1;
            ny = hy;
        }//현재 방향이 왼
        else if (dirX == dx[3] && dirY == dy[3]) {
            nx = hx + 1;
            ny = hy;
        }
    }
    //머리를 오른쪽으로 꺾음
    else if (direction[cnt] == 'D') {
        //현재 방향이 아래쪽
        if (dirX == dx[0] && dirY == dy[0]) {
            nx = hx;
            ny = hy - 1;
        }//현재 방향이 위쪽
        else if (dirX == dx[1] && dirY == dy[1]) {
            nx = hx;
            ny = hy + 1;
        }//현재 방향이 오른
        else if (dirX == dx[2] && dirY == dy[2]) {
            nx = hx + 1;
            ny = hy;
        }//현재 방향이 왼
        else if (dirX == dx[3] && dirY == dy[3]) {
            nx = hx - 1;
            ny = hy;
        }
    }
    //머리를 꺾지 않음
    else{
        nx = hx + dirX;
        ny = hy + dirY;
    }
    
    return Move(nx, ny, hx, hy, cnt + 1);
}


int main() {
    cin >> N >> K;
    
    while (K--) { // 사과 위치 저장
        int x, y;
        cin >> x >> y;
        map[x - 1][y - 1] = 2;
    }
    cin >> L;
    while (L--) { // 시간에 따른 뱀의 회전방향 저장
        int x;
        char c;
        cin >> x >> c;
        direction[x] = c;
    }
    q.push({ 0,0 });
    int ans = Move(0, 0, 0, -1, 0); //처음엔 오른쪽으로 시작함.
    cout << ans;
}

 

참고: https://luv-n-interest.tistory.com/1215