BOJ/백준 3190 뱀

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

 

해결 아이디어 

문제를 읽어보니 시뮬레이션 문제인거 같았다 솔직히 구현은 그냥 주어진대로 코드를 작성하면 될 것 같았고

중요한건 방향전환 부분과 몸이 벽이나 몸이 부딛칠때 그 부분을 처리하는게 중요한 것 같았다.

 

솔직히 말하면 방향전환 부분은 자력으로 해결하지는 못했고 인터넷 검색을 통해 알게 되었고 이를 바탕으로 해결하게 되었다.

int dx[] = {0, 1, 0, -1}; // 오른쪽, 아래, 왼쪽, 위
int dy[] = {1, 0, -1, 0};

dir = (dir + 3) % 4; // 왼쪽으로 90도 회전
dir = (dir + 1) % 4; // 오른쪽으로 90도 회전

이 부분이 방향전환 핵심 아이디어이다 

 

먼저, 뱀의 방향은 정수로 표현된다

0: 오른쪽 1: 아래쪽 2: 왼쪽 3: 위쪽 이렇게 설정된 방향을 바탕으로 두 가지 회전 방식이 있고

1. 왼쪽으로 90도 회전 
왼쪽으로 90도 회전 dir + 3는 현재 방향에서 3을 더하는 것. 이는 왼쪽으로 90도 회전하는 효과를 준다.
예를 들어, 현재 방향이 0 (오른쪽)인 경우: dir = 0 + 3 = 3 (위쪽)
현재 방향이 1 (아래쪽)인 경우: dir = 1 + 3 = 4 % 4 = 0 (오른쪽)
현재 방향이 2 (왼쪽)인 경우: dir = 2 + 3 = 5 % 4 = 1 (아래쪽)
현재 방향이 3 (위쪽)인 경우: dir = 3 + 3 = 6 % 4 = 2 (왼쪽)
% 4는 방향이 0에서 3 사이로 유지되도록 보장해줌. 즉, 방향이 4 이상이거나 0 미만으로 넘어가지 않도록 한다.

2. 오른쪽으로 90도 회전
오른쪽으로 90도 회전 dir + 1은 현재 방향에서 1을 더하는 것. 이는 오른쪽으로 90도 회전하는 효과를 줍다.
현재 방향이 0 (오른쪽)인 경우: dir = 0 + 1 = 1 (아래쪽)
현재 방향이 1 (아래쪽)인 경우: dir = 1 + 1 = 2 (왼쪽)
현재 방향이 2 (왼쪽)인 경우: dir = 2 + 1 = 3 (위쪽)
현재 방향이 3 (위쪽)인 경우: dir = 3 + 1 = 4 % 4 = 0 (오른쪽)
마찬가지로 % 4를 통해 방향이 항상 0에서 3 사이로 유지되도록 한다.

 

이것을 바탕으로 작성한 코드

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

using namespace std;

int dx[] = {0, 1, 0, -1}; // 오른쪽, 아래, 왼쪽, 위
int dy[] = {1, 0, -1, 0};

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

    int n, k, l;
    cin >> n;
    cin >> k;

    vector<vector<int>> board(n + 1, vector<int>(n + 1, 0)); // 1-indexed board
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        board[x][y] = 1; // 사과가 있는 위치
    }

    cin >> l;
    vector<pair<int, char>> directions; // 방향 전환 정보
    for (int i = 0; i < l; i++) {
        int sec;
        char order;
        cin >> sec >> order;
        directions.push_back({sec, order});
    }

    deque<pair<int, int>> snake; // 뱀의 위치 (x, y)
    snake.push_front({1, 1}); // 초기 위치
    int dir = 0; // 초기 방향 (오른쪽)
    int time = 0; // 경과 시간
    int index = 0; // 방향 전환 인덱스

    while (true) {
        time++;

        // 뱀의 머리 위치 계산
        int head_x = snake.front().first + dx[dir];
        int head_y = snake.front().second + dy[dir];

        // 벽이나 자기 몸에 부딪히면 게임 종료
        if (head_x < 1 || head_x > n || head_y < 1 || head_y > n || 
            find(snake.begin(), snake.end(), make_pair(head_x, head_y)) != snake.end()) {
            break;
        }

        // 뱀의 머리를 이동
        snake.push_front({head_x, head_y});

        // 사과가 있는지 확인
        if (board[head_x][head_y] == 1) {
            board[head_x][head_y] = 0; // 사과 먹음
        } else {
            // 사과가 없으면 꼬리 위치를 제거
            snake.pop_back();
        }

        // 방향 전환 처리
        if (index < l && directions[index].first == time) {
            if (directions[index].second == 'L') {
                dir = (dir + 3) % 4; // 왼쪽으로 90도 회전
            } else {
                dir = (dir + 1) % 4; // 오른쪽으로 90도 회전
            }
            index++;
        }
    }

    cout << time << '\n'; // 게임 종료 시간 출력

    return 0;
}

 

그리고 이번 문제를 풀면서 알게 된 사실인데 deque가 인덱스로 접근 가능하다는 것을 처음 알았다.

처음에는 그냥 queue를 사용해서 풀려고 해맸으나 deque가 인덱스 접근이 가능하다는 사실을 알고 문제를 해결했다.

 

그리고 로컬에서는 알고리즘 헤더 없이도 find함수가 잘 작동하길레 제출했으나 컴파일 에러를 3번이나 맞고 알고리즘 헤더를 작성하지

않아서 문제가 발생한 것을 알게 되었다.

 

마지막으로 저 방향전환 부분은 외워둬는게 좋을것 같다.