[BOJ] 백준 3190 뱀 c++ (구현, deque)

문제 출처 : https://www.acmicpc.net/problem/3190

3190번: 뱀

---

풀이

처음에 단순 구현으로 생각했으나, 문제를 보면 꼬리를 제거해야 하는 경우도 있고 머리 부분을 추가하는 경우도 있다.

즉 처음과 끝을 push, pop할 수 있어야 했기에 deque을 사용하기로 하였다.

방향 회전시키기

단순 구현이라 특별한 로직같은건 없으나 방향을 90도 회전 시켜야 할 경우에는 다음과 같이 풀이하였다.

• 인덱스를 접근할 dx, dy 배열을 선언한다. (상 우 하 좌 순서로 선언함)
• 현재 어떤 방향인지 알려줄 dir_idx 변수를 선언한다.
• 오른쪽 회전일 경우 +1 후 %4로 처리, 왼쪽일경우 -1 + 4후 %4로 처리한다.
• dx[dir_idx], dy[dir_idx]로 사용하면 된다.

int dir_idx = 1; // 방향 상우하좌
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

... 

if(ch == 'D')
    dir_idx = (dir_idx + 1) % 4;
else dir_idx = (dir_idx - 1 + 4) % 4;

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>

using namespace std;

int arr[101][101]; // 1 뱀 2 사과
int N, K, L;
int ans;
int dir_idx = 1; // 방향 상우하좌
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N >> K;
    for(int i = 0; i < K; i++){
        int row, col;
        cin >> row >> col;
        arr[row][col] = 2;
    }

    cin >> L;
    queue<pair<int, char>> time;
    for(int i = 0; i < L; i++){
        int X; char C;
        cin >> X >> C;
        time.push({X, C});
    }

    arr[1][1] = 1;    
    deque<pair<int, int>> dq;
    dq.push_back({1, 1});

    while(1){
        ans++;
        int nRow = dq.back().first + dy[dir_idx];
        int nCol = dq.back().second + dx[dir_idx];
        if(nRow <= 0 || nRow > N || nCol <= 0 || nCol > N || arr[nRow][nCol] == 1) 
            break;

        if(arr[nRow][nCol] != 2){
            arr[dq.front().first][dq.front().second] = 0;
            dq.pop_front();
        }
        arr[nRow][nCol] = 1;
        dq.push_back({nRow, nCol});

        if(ans == time.front().first){
            char ch = time.front().second;
            if(ch == 'D')
                dir_idx = (dir_idx + 1) % 4;
            else dir_idx = (dir_idx - 1 + 4) % 4;
            time.pop();
        }
    }
    cout << ans << '\n';
}