[백준] 3190번: 뱀 (C++)

 

www.acmicpc.net/problem/3190

3190번: 뱀

이차 원 배열 M에 사과는 1로 표시하고, 뱀의 몸은 -1로 표시를 하였다. int 변수 dx와 dy를 통해서 현재 진행방향을 나타 냈다.

 

벽 또는 자신의 몸에 부딪힐 때 종료 조건을 걸고 break 했다.

 

몸이 되는 부분의 차례로 큐에 넣어서 사과를 먹지 않았을 때 꼬리 부분(가장 나중에 큐에 들어간 부분)을 없앴다.

 

위, 아래, 오른쪽, 왼쪽 진행 방향 각각에 대해서 'L'과 'D'일 때를 처리해 주었다. -> 이 부분을 좀 더 간단하게 표현할 수 있을 것 같다.

 

방향 전환 정보들도 cmd라는 queue에 넣어서 수행하면 pop 하는 식으로 구현했다.

 

소스코드

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

int n, k, x, cnt;
int M[101][101];
queue<pair<int, char> > cmd;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        M[a][b] = 1; // 사과
    }

    cin >> x;
    for (int i = 0; i < x; i++) {
        int a;
        char b;
        cin >> a >> b;
        cmd.push(make_pair(a, b));
    }

    int x = 1, y = 1;
    int dx = 0, dy = 1;
    queue<pair<int, int> > q;
    M[x][y] = -1; // 뱀의 몸은 -1
    q.push(make_pair(x, y));

    while (true) {    
        cnt++;
        x += dx;
        y += dy;
		
         // 종료조건
        if (x <= 0 || x > n || y <= 0 || y > n || M[x][y] == -1) break;

        if (M[x][y] != 1) {	// 사과가 아닐때
            M[q.front().first][q.front().second] = 0;	// 꼬리를 지워준다.
            q.pop();
        }
        M[x][y] = -1; // 머리를 위치시킨다.
        q.push(make_pair(x, y)); // 새로운 몸의 부분을 큐에 넣는다.
        

        if (cmd.front().first == cnt) {	// 방향 전환 타이밍일때
            if (cmd.front().second == 'L') { // 왼쪽으로 돌려야함
                if (dx == 0 && dy == 1) { // 오른쪽 진행 -> 위로 진행으로 바꾼다.
                    dx = -1;
                    dy = 0;
                } else if (dx == 1 && dy == 0) { // 아래 진행 -> 오른쪽 진행으로 바꾼다.
                    dx = 0;
                    dy = 1;
                } else if (dx == 0 && dy == -1) {  // 왼쪽 진행 -> 아래 진행으로 바꾼다.
                    dx = 1;
                    dy = 0;
                } else if (dx == -1 && dy == 0) { // 위 진행 -> 왼쪽 진행으로 바꾼다.
                    dx = 0;
                    dy = -1;
                }
            } else { // 오른쪽으로 돌려야함: 위와 같은 방식
                if (dx == 0 && dy == 1) {
                    dx = 1;
                    dy = 0;
                } else if (dx == 1 && dy == 0) {
                    dx = 0;
                    dy = -1;
                } else if (dx == 0 && dy == -1) {
                    dx = -1;
                    dy = 0;
                } else if (dx == -1 && dy == 0) {
                    dx = 0;
                    dy = 1;
                }
            }
        cmd.pop(); // 수행했으니 삭제해줌
        }

    }

    cout << cnt;
    return 0;
}