[BOJ알고리즘, C++]#3190_뱀, deque, map

#1. 문제

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

 

---

 

#2. 풀이

 

1. deque

[Basic C++] #68_deque

C++의 STL에서 제공하는 deque 컨테이너는 양방향 자료구조로 구현되어 컨테이너의 양쪽 끝에서 삽입/삭제 연산을 모두 활용할 수 있는 특징이 있습니다. 

 

2. map

[Basic C++] #38_map, 연관 컨테이너

C++의 STL에서 제공하는 map 컨테이너는 키와 값을 한 쌍으로 레드-블랙 트리 자료구조에 저장하는 연관 컨테이너입니다. map 컨테이너는 키의 중복을 허용하지 않고, 내부적으로 정렬된 상태를 유지하는 특징이 있습니다.

 

3. 방향 전환 정보는 map 컨테이너에, 뱀의 위치 정보는 deque 컨테이너에!

1. 먼저, 보드의 사과 정보를 별도의 2차 vector 컨테이너에 bool 형으로 저장합니다.(true 일 경우 사과가 존재하는 걸로)
2. 그리고, 방향 전환 정보는 map 컨테이너에 { 방향 전환 시간, 오른쪽/왼쪽 여부 } 형식으로 저장합니다.
3. 시간이 증가함에 따라서 deque의 첫 번째 항목(뱀의 머리 위치 정보)을 다음 위치로 이동시키고 벽에 부딪히거나, 혹은 몸에 부딪혔는지 확인해 줍니다. 그리고, 사과를 먹었는지 확인한 뒤에 새로운 머리 위치를 deque의 첫 번째 항목으로 삽입해 주고, 방향 전환 여부를 확인합니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/3190
*   @문제: 'Dummy' 게임, 사과 위치와 뱀의 이동 경로가 주어지면 해당 게임이 몇 초에 끝나는지 계산
*   @설명
        1. 덱 자료구조 활용
        2. '방향 전환' 다음 방향을 설정할 때, 분자가 -1이 되어 연산이 실패할 수도 있으니 왼쪽의 경우 +3해주자
*/


#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <deque>
#include <set>
using namespace std;

#define MAX 101

int N, K, L;
vector<vector<bool>> board(MAX, vector<bool>(MAX, false));
map<int, char> m;
// @방향: 오른쪽? 현재 (index+1)%4, 왼쪽? 현재 (index-1)%4
int dy[] = {0, 1, 0, -1};
int dx[] = {1, 0, -1, 0};

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

    cin >> N; 
    cin >> K;

    while(K--)
    {
        int row, col;
        cin >> row >> col;

        board[row][col] = true;
    }

    cin >> L;

    while(L--)
    {
        int X;
        char C;

        cin >> X >> C;

        m.insert({X,C});
    }

    deque<pair<int,int>> dq;
    // @현재 방향
    int direction = 0; 
    int time = 0;

    dq.push_back({1,1});

    while(true)
    {
        time++;

        int ny = dq.front().first + dy[direction];
        int nx = dq.front().second + dx[direction];

        //@종료 조건1 : 벽
        if(ny <= 0 || ny > N || nx <= 0 || nx > N) break;
        //@종료 조건2 : 몸에 부딪힘
        set<pair<int, int>> snake_body(dq.begin(), dq.end());
        if(snake_body.find({ny, nx}) != snake_body.end()) break;

        //@사과 없음
        if(!board[ny][nx]) dq.pop_back();
        else board[ny][nx] = false;

        dq.push_front({ny,nx});

        //@방향 전환 여부
        if(m.find(time) != end(m))
        {
            if(m[time] == 'L') direction = (direction + 3) % 4;
            else if(m[time] == 'D') direction = (direction + 1) % 4;
        }
    }

    cout << time;

    return 0;
}

 

---