[C++] BOJ 3190번: 뱀

문제

1. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
2. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
3. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

 

*처음 봤을때 턴에 관한 개념이 잘 생성되지 않았는데 턴은 무조건 한번만 실행되는 시스템이다.

 

 

입력 1

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

출력 1

9

 

입력 2

10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

출력 2

21

 

입력 3

10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

출력 3

13

 

 

코드

#include<iostream>
//#include<Windows.h>
#include<deque>
#include<vector>

using namespace std;

int main() {
    
    int N, K,L;     //N : 보드의 크기, K : 다음 줄에 사과의 개수, L : 뱀의 방향 변환 횟수
    int column, row;
    int currentX=0, currentY=0;
    int arrIdx = 0, turnIdx=0;          //arrIdx : 방향배열 인덱스, turnIdx : 방향 회전배열 인덱스
    int arrow[4][2] = { {1,0},              //오른쪽
                        {0,1},              //아래
                        {-1,0},             //왼쪽
                        {0,-1} };           //위
    deque<vector<int>> body;

    cin >> N;

    //해당 배열만큼 2차원 행렬 만들기
    int** board = new int* [N];
    for (int i = 0; i < N; i++) {
        board[i] = new int[N];
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            board[i][j] = 0;
        }
    }

    board[0][0] = 1;
    vector<int> point;
    point.push_back(0);
    point.push_back(0);
    body.push_back(point);

    cin >> K;
    for (int i = 0; i < K; i++) {
        cin >> row >> column;
        board[row-1][column-1] = 2;
    }
    cin >> L;
    int* turn = new int[L];
    int* direction = new int[L];
    int lValue;
    char rValue;

    for (int i = 0; i < L; i++) {
        cin >> lValue >> rValue;
        turn[i] = lValue;
        direction[i] = rValue;
    }

    int time = 0;

    while (time < 10000) {
    
        /* {
            Sleep(1000);
            system("cls");

            cout << "Time :" << time+1 << endl;
            //출력해서 확인하기
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    cout << board[i][j] << " ";
                }
                printf("\n");
            }
        }*/
        
        if (time == turn[turnIdx] && time != 0) {
            if (direction[turnIdx] == 'D') {
                arrIdx++;
            }
            if (direction[turnIdx] == 'L') {
                arrIdx--;
            }
            turnIdx++;
        }


        if (arrIdx > 3)
            arrIdx = arrIdx % 4;
        if (arrIdx < 0) {
            arrIdx = 4 + arrIdx;
        }

        //오른쪽으로 이동하는 것
        currentX += arrow[arrIdx][0];
        currentY += arrow[arrIdx][1];
       
        if ((currentX < 0 || currentX >= N) ||(currentY < 0 || currentY >= N))
            break;
        if (board[currentY][currentX] == 1)
            break;

        if (board[currentY][currentX] == 2) {
            //만약 사과가 있다면
            point.clear();
            point.push_back(currentY);
            point.push_back(currentX);
            body.push_front(point);

            for (size_t i = 0; i < body.size(); i++) {
                board[body[i][0]][body[i][1]] = 1;
            }
        }
        else {
            //맨끝의 값의 자리를 0으로 바꿔주기
            board[body.back()[0]][body.back()[1]] = 0;
            //처음의 값을 뒤로 밀어주기

            for (size_t  i = body.size() - 1; i >0 ; i--) {
                int temp = body[i-1][0];
                body[i][0] = temp;
                temp = body[i-1][1];
                body[i][1] = temp;
            }

            //첫번째 머리움직이기
            body[0][0]= currentY;
            body[0][1]= currentX;

            for (size_t i = 0; i < body.size(); i++) {
                board[body[i][0]][body[i][1]] = 1;
            }
        }

        time++;
    }

    cout << time + 1;

    //할당 해제
    for (int i = 0; i < N; i++)
        delete[] board[i];

    return 0;
}

 

*간단한 해설*

턴에 관한 개념이 처음에 잡히지 않아서 반복적으로 생성되는 줄 알고 시간을 많이 사용했다.

    Sleep(1000);
    system("cls");

    cout << "Time :" << time+1 << endl;
    //출력해서 확인하기
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << board[i][j] << " ";
        }
        printf("\n");
    }

이부분의 주석처리를 빼면 어떻게 실행되는지 확인해볼 수 있다.

예제의 3개의 출력 과정은 아래와 같다.

0이 빈칸이고 1은 뱀, 2는 사과이다.

 

예제 1

예제 2

예제 3

사실 여기까지 와서 예제를 넣어보았을 때 제출을 하니까 틀린것으로 나왔었다.

테스트 케이스를 여러개 해보지 않아서 그런데 반례 케이스를 모아놓은 사이트를 찾았다.

https://www.acmicpc.net/board/view/56469

글 읽기 - 뱀 문제 반례모음입니다

나의 경우 맨 처음 반례 케이스의 5번째까지 통과를 하니 통과를 할 수 있었다.

 

다른 분의 알고리즘을 찾아보니 이분꺼가 깔끔하게 정리되어 있었다.

내 코드는 for문을 많이 쓰는데 for문을 많이 쓰지 않도록 생각하는 힘을 좀 더 길러야겠다.

https://velog.io/@nacean/%EB%B0%B1%EC%A4%803190-%EB%B1%80-C-%ED%92%80%EC%9D%B4

백준[3190] 뱀 C++ 풀이

 

 

 

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*