[백준 3190] 뱀 (C++)

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

 

구현

그 snake 게임? 생각하면 될 듯

N * N 보드에서 길이 1짜리 뱀으로 시작해서 한칸씩 늘리면서 이동하면서

도처에 위치한 사과들을 먹으면 길이가 +1 되고, 못 먹으면 길이가 유지되는 (그래서 꼬리가 이동함 - 사라짐)

입력으로는 사과의 위치와 S초후에 바뀌는 방향이 주어진다.

-> 머리의 방향을 바꿔가면서 한칸씩 이동하는 스네이크 게임~

종료 조건: 벽에 닿거나, 본인과 본인의 머리가 부딪힐 경우

 

접근방법

구현문제여서 시뮬레이션으로 풀었다.

- 정사각보드 구성: 2차원배열로 격자판을 만들어 놓고, 빈칸은 0, 뱀은 1, 사과는 2로 설정했다.

- 뱀의 이동 방향: 오른쪽, 아래, 왼쪽, 위 순서대로 방향 배열 선언해둠 (dr, dc), 왼쪽으로 바꾸는거면 방향 인덱스 +3, 오른쪽이면 방향 인덱스+1 (%4)

현재 위치 좌표 값 저장해두고 현재 이동 방향대로 한칸씩 이동하면서, 이동할 때마다 새로 방문하는 곳 좌표를 큐에 모두 넣어줬다 (꼬리지워야하기 때문)

생존여부 체크하고, 사과 만났을 때는 따로 처리할 게 없고, 사과를 못만났을 때만 꼬리칸을 0으로 만들어줘야함.

사과의 여부와 상관없이 현재 머리가 이동한 칸은 1로 바뀌기 때문에 한꺼번에 처리하면 됨

 

오답노트

- 반복문에서 시간을 어디서 부터 시작해야하는지 고민이 됐었음..예제 답 나오는거 보고 했는데 while 문으로 할 때는

반복문 들어가기 전에 0으로 초기화하고, 들가자마자 1 더함

- 원래 for문으로 돌렸다가 max를 못잡겠어서 while로 바꿈

- 왼쪽으로 돌 때 인덱스-1 % 4 이렇게 했었는데 갑자기 음수 모드 연산 헷갈려서 그냥 +3으로 함

- 그리고 마지막 결정적 실수 요인.. 인덱스+1 %4 에서 앞에 괄호처리 안해줘서 틀렸었음.. (인덱스+1) %4 꼬옥해주시길..

 

 

 

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;

struct Point {
    int r;
    int c;
};

int main(){
    // input
    
    int N, K;
    cin >> N >> K;
    
    vector<vector<int>> adj(N+1, vector<int>(N+1,0));
    
    //사과
    for(int i = 0; i < K; i++){
        int r,c;
        cin >> r >> c;
        adj[r][c] = 2;
    }
    
    int L;
    cin >> L;
    map<int, char> m;
    for(int i = 0; i < L; i++){
        int x;
        char c;
        cin >> x >> c;
        m.insert({x, c});
    }
    
    adj[1][1] = 1;
    int dr[4] = {0,1,0,-1};
    int dc[4] = {1,0,-1,0};
    //왼 L 오 D
    //D -> +1 % 4, L -> +3 % 4
    int cur_dir_idx = 0;
    int cr = 1;
    int cc = 1;
    
    //꼬리
    queue<Point> tail;
    Point p;
    p.r = 1;
    p.c = 1;
    tail.push(p);
    
    int result = 0;
    int s = 0;
    while(1){
        s++;
        
        cr += dr[cur_dir_idx];
        cc += dc[cur_dir_idx];
        
        //생존 확인
        if(cr > N || cc > N || cr < 1 || cc < 1 || adj[cr][cc] == 1){
            result = s;
            break;
        }
        
        //사과 확인
        if(adj[cr][cc] == 0){ //없
            Point t = tail.front();
            adj[t.r][t.c] = 0;
            tail.pop();
        }
        adj[cr][cc] = 1;
        p.r = cr;
        p.c = cc;
        tail.push(p);
        
        // 맵 확인 -> 방향 전환
        if(!m.empty() && m.begin()->first == s){
            char d = m.begin()->second;
            if(d == 'L'){
                cur_dir_idx = (cur_dir_idx+3) % 4;
            }else{
                cur_dir_idx = (cur_dir_idx+1) % 4;
            }
            m.erase(m.begin());
        }
    }
    
    cout << result;
    
    return 0;
}