백준 3190 뱀 c++ [컴공과고씨]

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

3190번: 뱀

 

문제 해결 방법은 2차원 배열을 이용해서 map을 만들어주고 사과가 있는 칸에는 1을 넣어준다.

입력으로 시간과 방향 정보를 받아 준다. 

방향을 바꾸기 전까지 반복문을 돌아줄건데 다음 x좌표와 다음 y 좌표를 구해주고 맵을 벗어나는지 확인해주고 visit을 체크해줄건데 visit은 몸이 있는 좌표에 true를 넣어주는 것이다. 뱀이 사과를 먹는 경우에 몸의 길이가 늘어나는데 이때 큐에 좌표를 넣어주고 visit에 true를 넣어준다. 만약 사과가 없는 칸에 갔을 때는 큐에서 pop을 해주고 visit를 false로 만들어주면된다. 이렇게 큐를 이용해서 꼬리부터 몸까지 좌표를 표시할 수 있다.

그 후 방향 정보를 정하는 방법은 

이렇게 %를 이용해서 만들어 줄 수 있다. 나는 우측을 0으로 놓았다.

 

이렇게 반복 후 방향까지 회전한 후 마지막에는 뱀이 부딪힐때까지 쭉 보내줘야 함에 주의하자 << 이거 때문에 40분을 날렸습니다....

 

전체코드

#include <iostream>
#include <queue>
using namespace std;
int main(){
    int n, t1, t2 , k;
    int map[102][102] = {0};
    bool visit[102][102] = {false};
    cin >> n;
    cin >> k;
    for (int i = 0; i < k; i++){
        cin >> t1 >> t2;
        map[t1 - 1][t2 - 1] = 1;
    } // 문제에서 원점을 1,1을 기준으로 하고 있고 나는 0,0을 원점으로 하기위해서 -1해줌.
 
    int cnt = 0;
    char t3;
 
    int dx[4] = {1, 0, -1, 0}; // 우, 하, 좌, 상
    int dy[4] = {0, 1, 0, -1};
    int dir = 0;
    int x = 0;
    int y = 0;
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    int bt1 = 0;
    int l;
    cin >> l;
    for (int i = 0; i < l;i++){
        cin >> t1 >> t3;
        
        while(cnt < t1 || i == l-1){ 
            // 마지막 입력까지 게임이 끝나지 않을 경우 뱀을 끝날때까지 보내줘야함.
            cnt++;
            int nx = x + dx[dir];
            int ny = y + dy[dir];
 
            if(nx >=0 && ny >=0 && nx<n && ny<n && !visit[ny][nx]){
                // 게임이 끝나지 않을 조건
                if(map[ny][nx] == 1){ // 사과를 먹었을 때
                    map[ny][nx] = 0; // 사과 없애주고
                    q.push(make_pair(nx, ny)); // 몸 좌표에 추가
                    visit[ny][nx] = true; // 몸 있다는걸 좌표 표시
                }else{// 사과 없을 때
                    q.push(make_pair(nx, ny)); 
                    visit[ny][nx] = true; 
                    visit[q.front().second][q.front().first] = false;
                    // 꼬리 부분없애주기
                    q.pop();
                }
            }else{
                cout << cnt;
                return 0;
            }        
            x = nx;
            y = ny;
            if(cnt == t1){
                if(t3 == 'D'){ // 우측 회전
                    dir = (dir + 1) % 4; 
                }else{ // 좌측 회전
                    dir = (dir + 3) % 4;
                }
            }
        }
    }
    return 0;
} // 1h

체감 난이도	걸린시간	후기	참고	사용 알고리즘
중하	1h	입력이 끝난 후 게임을 끝날 때 까지 뱀을 보내주어야하는데 그걸 생각하지 않아서 시간을 많이 씀.	x	큐 (queue)