[BOJ 3190] 뱀 (C++)

www.acmicpc.net/problem/3190

3190번: 뱀

뱀 문제

 

구현 방법

1) 뱀 표현

뱀을 표현하기 위해 큐(Queue) 자료 구조를 사용했습니다.

뱀이 몸길이를 늘려 머리를 다음칸에 위치 시킬때 하나 push 해서 queue를 늘립니다.

만약 해당 칸에 사과가 있었다면 꼬리 이동을 하지않고, 빈칸이면 꼬리를 없애주는 pop을 해줍니다.

 

머리를 놓은 새로운 자리에 2 라고 뱀을 표기해주고, 꼬리가 사라지는 자리에는 0을 넣어주며 arr배열에 뱀의 몸통 표시를 해주었습니다.

2) 방향 전환 방법

일단 뱀이 움직일 판을 arr[102][102]로 선언해주고, 이동할 때 사용할 방향 배열을 다음과 같이 선언해 주었습니다.

 

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1 ,0};

 

이 배열은 인덱스가 0일 때는 y만 dy만 1이므로 y만 증가하고, 인덱스가 1일 때는 dx만 1이므로 x만 증가합니다.

 

초기에는 뱀이 오른쪽을 바라보고있으니, y만 증가하는 것으로 시작해 오른쪽, 왼쪽 방향 전환을 다음과 같이 사용했습니다.

 

오른쪽으로 방향 전환 : dir = (dir+1)%4;

왼쪽으로 방향 전환 : dir = (dir+3)%4;

여기서 dir이 dx, dy배열에 사용될 index입니다.

 

인덱스가 0일때는 오른쪽 방향으로 전진하니 y만 증가하다가, 오른쪽으로 방향 전환을 하면 (dir+1)%4로 인해 1이 돼서 x값만 증가하는 아래 방향을 보게 됩니다.

 

또는 인덱스가 0일 때 오른쪽 방향으로 전진하니 y값 만 증가하다가, 왼쪽으로 방향 전환을 하면 (dir+3)%4로 인해 3이 돼서 x값만 감소하는 위쪽 방향을 보게 됩니다.

	x값 감소
y값 감소	뱀	y값 증가
	x값 증가

 

3) 방향 전환 정보 사용

방향 전환 정보가 x초 때 c방향으로 전환된다는 형식으로 "8 D"로 입력이 됩니다.

해당 입력은 8초 때 D 방향으로 전환을 한다는 의미입니다.

 

해당 정보를 pair <int, char> 형태로 turnInfo라는 벡터에 저장시켰습니다.

문제 조건에 시간 순으로 주어진다 하니 정렬은 생략했습니다.

 

뱀 게임 시작 후 지나간 시간과 turnInfo 벡터의 첫 번째 원소의 시간과 일치하면 방향을 전환해줍니다.

 

3) 전체 로직

위 내용을 바탕으로 뱀 게임의 전체적인 로직은 하나의 while문안에서 처리됩니다.

 

1) 시간을 1초씩 증가시킵니다.

2) 뱀의 머리를 방향대로 한 칸 전진시킵니다.

   i) 해당 칸이 벽이나 몸통인 경우 현재 시간을 출력하고 프로그램을 종료합니다.

   ii) 해당 칸이 빈칸이면 꼬리를 제거해줍니다.

   iii) 해당 칸이 벽, 몸통, 빈칸이 모두 아니면 사과 이므로 꼬리 제거 로직을 건너뛰고 몸길이를 늘려줍니다.

6) 입력받은 방향 전환 시간과 현재 시간이 일치하면 방향 전환을 해줍니다.

 

 

소스 코드

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

int arr[102][102];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

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

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

    //사과 위치 표시
    for(int i=0;i<k;i++) {
        int x, y;
        cin >> x >> y;
        //사과 표시 (4)
        arr[x][y] = 4;
    }

    //방향 전환
    int L;
    cin >> L;
    //방향 전환 저장할 벡터
    vector<pair<int, char>> turnInfo;

    //방향 전환 입력 받음 (L개)
    for(int i=0;i<L;i++) {
        int sec;
        char dir;
        cin >> sec >> dir;
        turnInfo.push_back({sec, dir});
    }


    int time =0;
    pair<int, int> head = {1,1};
    int dir = 0;
    int index = 0;
    queue<pair<int, int>> snake;
    //출발 지점에 뱀 표시 (2 이면 뱀)
    arr[1][1] = 2;
    snake.push(head);

    //게임 시작
    while(1) {
        //1초 추가
        time++;

        //머리 전진
        head.first += dx[dir];
        head.second += dy[dir];
        int nx = head.first;
        int ny = head.second;

        //벽, 몸통인경우
        if(nx > n || ny > n || nx < 1 || ny < 1 || arr[nx][ny] == 2) {
            cout << time;
            return 0;
        }//빈칸이면 꼬리 제거
        else if(arr[nx][ny] == 0) {
            pair<int, int> cur = snake.front();
            snake.pop();
            arr[cur.first][cur.second] = 0;
        }

        //벽, 몸통, 빈칸 아니면 꼬리 제거 안하고 머리 push
        arr[nx][ny] = 2;
        snake.push({nx, ny});

        //입력받은 방향 전환 시간과, 현재 시간이 일치하면 방향 전환
        if(time == turnInfo[index].first) {
            if(turnInfo[index].second == 'D') {
                //오른쪽으로 회전
                dir = (dir+1)%4;
                index++;
            } else if(turnInfo[index].second == 'L') {
                //왼쪽으로 회전
                dir = (dir+3)%4;
                index++;
            }
        }
    }
}