[백준] 3190번: 뱀

 

시뮬레이션 문제이다.

 

 

 

 

 

풀이 방식(성공)

 

이러한 시뮬레이션 문제는 직관적인 경우가 많아 코드 구현만 잘 한다면 문제없이 통과하는 경우가 많았고,

이 문제도 그러한 문제들 중 하나였다. while 구문을 통해 시간을 점점 증가시키고, 탈출 조건만 잘 설정하면 될 것이다.

머리와 꼬리부분은 충돌 체크나 사과를 먹을 때 빨리 업데이트하기 위해 변수로써 두었고, bodyCheck라는 2차원 배열을 따로 두어 구현하였다. 뱀이 방향을 바꾸는 부분은 우,하,좌,상 시계방향 순서로 배열을 두고 'L'이라면 moveIndex를 감소, 'D'라면 moveIndex를 증가시켰다.

나중에 deque 자료구조를 활용하기에 최적화된 문제라 생각이 들었고 일부분을 적용시켰다. 따라서 최적화를 한다면 따로 변수를 정의하지 않아도 앞과 뒤를 빠르게 접근할 수 있는 deque로 코드가 깔끔하게 작성될 것이다. 

 

다만 코드 작성 후 예제는 맞았으나 최종적으로 통과하지 못했는데, 이유를 찾는 데 어려움이 있었다.

그 이유는 "사과를 먹은 후 삭제"하는 과정을 포함시키지 않았기 때문이었다. 따라서 사과가 있는 곳을 지나칠때마다 뱀은 점점 커졌고, 옳지 않은 결과로 이어졌다. 따라서 //TODO 부분을 수정하였다.

#include <iostream>
#include <queue>
 
using namespace std;
 
int N, K; //N 보드의 크기, K 사과의 개수
int L; //방향 전환 횟수
int map[101][101]; //게임 맵, 전역변수 자동초기화
bool bodyCheck[101][101];
queue<int> times;
queue<char> tran;
//우, 하, 좌, 상
int dir_x[] = {1, 0, -1, 0};
int dir_y[] = {0, 1, 0, -1};
 
int main(){
 
    cin >> N >> K;
    for(int i=0; i<K; i++){
        int y, x;
        cin >> y >> x;
        map[y][x] = 1; //사과의 위치
    }
 
    cin >> L; 
    for(int i=0; i<L; i++){
        int t;
        char d;
        cin >> t >> d;
        times.push(t);
        tran.push(d);
    }
    pair<int, int> head = {1,1}; //head.first = y, head.second = x
    pair<int, int> tail = {1,1}; //tail.first = y, tail.second = y
    bodyCheck[1][1] = true;
    int elapsedTime = 0;
    int moveIndex = 0; //0 우, 1 하, 2 좌, 3 상
    deque<pair<int, int>> snakeInfo;
    snakeInfo.push_back(head);
    while(1){
        elapsedTime++;
        
        head.first += dir_y[moveIndex]; //y축 이동
        head.second += dir_x[moveIndex]; //x축 이동
        
        if(head.second < 1 || head.second > N || head.first < 1 || head.first > N 
            || bodyCheck[head.first][head.second] == true){
            cout << elapsedTime;
            break;
        }
        bodyCheck[head.first][head.second] = true;
        snakeInfo.push_front(head);
 
        if(map[head.first][head.second] != 1){ //사과가 없다면, 꼬리를 삭제, 재부여
            bodyCheck[snakeInfo.back().first][snakeInfo.back().second] = false; //꼬리 삭제
            snakeInfo.pop_back();
        }else{
            map[head.first][head.second] = 0; //TODO: 사과 지우기!!
        }
 
        if(!times.empty() && times.front() == elapsedTime){
            switch(tran.front()){
                case 'L': //왼쪽 방향
                    if(moveIndex-1 < 0){
                        moveIndex+=3;
                    }else{
                        moveIndex--;
                    }
                    break;
                case 'D': //오른쪽 방향
                    if(moveIndex+1 > 3){
                        moveIndex-=3;
                    }else{
                        moveIndex++;
                    }
                    break;
            }
            times.pop();
            tran.pop();
        }
    }
 
    return 0;
}
 

 

만약 이 문제가 코딩테스트에 출제되었다면 사과를 지우지 않았으므로 틀렸을 것이다. 테스트 케이스를 많이 작성해보거나 코드를 구현할 때 철저하게 분석하는 습관을 길러야겠다.