[Beakjoon] 3190 뱀 (C++)

문제 링크

BOJ 3190 : 뱀

문제

구현 문제이다.
N*N배열에서 뱀이 이동한다.
배열의 특정 위치에 사과가 존재한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

게임이 끝나는 시간을 구하는 문제이다.

풀이

구현 문제를 정말 오랜만에 풀었는데 이 문제 푸는데 1시간 넘게 시간을 썼다.
30분은 이게 왜 안돼 하면서 콘솔에 값을 출력해보며 디버깅을 했던 것 같다..

구현 문제를 풀 때마다 반성하는 거지만, 필요한 기능들을 명확히 구분해서 하나씩 구현하는 게 중요한 것 같다.

이 문제를 푸는데 필요한 기능들은
1. 뱀의 방향을 바꿔주는 것
2. 뱀을 진행 방향으로 이동시키는 것
3. 사과가 없는 경우 뱀의 꼬리 위치 칸을 비워주는 것
4. 사과가 있는 경우 사과를 없애고 뱀을 위치시키는 것
5. 시간을 진행시키면서 특정 시간마다 뱀의 방향을 바꿔주는 것
6. 게임 종료조건이 충족되면 게임을 종료시키는 것

대충 이정도인 것 같다.

방향을 바꾸는 로직은 get_dir()메서드로 따로 빼서 구현했다.
오른쪽으로 회전하는 경우와 왼쪽으로 회전하는 경우를 나눠서 dy[], dx[]배열의 인덱스를 조정해가며 진행 방향을 정의했다.

뱀의 길이를 줄이는 것은 queue를 이용해서 뱀이 존재하는 위치들을 저장해서 구현했다.

이런 시간이 진행되는 문제는 어떤 시점에서 시간을 업데이트해야하는지가 좀 헷갈린다.

코드

    #include<bits/stdc++.h>

    #define endl "\n"
    #define ll long long

    using namespace std;

    int matrix[101][101];
    int dy[] = {0,1,0,-1}; //우 하 좌 상
    int dx[] = {1,0,-1,0};

    int get_dir(int now, char turn){
        if(turn == 'D') now++;
        else if(turn == 'L') now--;
        
        if(now > 3) return 0;
        else if(now<0) return 3;
        else return now;
    }

    void Solve() {
        int N,K; cin>>N>>K;

        int r,c;
        for(int i=0; i<K; i++){
            cin>>r>>c;
            matrix[r][c] = 2;
        }

        int hy,hx; 
        hy = 1; hx = 1;
        queue<pair<int,int>> snake; snake.push({hy,hx});

        int L,X; char C;
        cin>>L;
        int time = 0, dir = 0;
        cin>>X>>C;
        while(true){
            time++;
            if(time > X&& L-->0) {
                dir = get_dir(dir,C);
                cin>>X>>C;
            }
            hy+=dy[dir]; hx+=dx[dir];
           
            if(hy>N||hx>N||hy<1||hx<1||matrix[hy][hx]==1) {
                cout<<time; return;
            }   

            //사과가 있으면 꼬리를 줄인다.
            if(matrix[hy][hx]!=2){
                matrix[snake.front().first][snake.front().second] = 0;
                snake.pop();
            }

            matrix[hy][hx] = 1;
            snake.push({hy,hx});
        }
        
        return;
    }


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

        return 0;
    }