[백준/BOJ 알고리즘] 3190 뱀 C++

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

3190번: 뱀

문제 설명이 잘 돼 있어 재밌게 풀었던 문제이다.

 

좌표를 나타내기 위해 pair를 사용하였다.

 

뱀이 차지하고 있는 공간(?)의 좌표를 큐에 담도록 한다.

기본적으로 뱀이 이동할 때 머리가 한칸 전진하고, 꼬리가 따라온다.

사과를 먹었다면 머리만 전진한다고 생각하면 이해가 쉽다. 

 

• 머리가 한칸 전진 : 새로운 좌표를 큐의 front에 PUSH
• 꼬리가 따라옴 : 큐의 end 값을 POP 

사과를 먹을 때 뱀이 길어진다. 사과의 좌표는 apple 배열에 담긴다.

뱀의 방향 전환 시간과 방향은 move 배열에 담긴다. 

방향 전환은 dir 배열에 상하좌우 값을 넣어놓고 나머지 연산을 통해 사용했다.

 

#include <stdio.h>
#include <deque>
using namespace std;
typedef std::pair<int, int> pr;
int main(){
    pr dir[4] = {make_pair(0,1),make_pair(1,0),make_pair(0,-1),make_pair(-1,0)}, apple[101];

    int move[10001] ={0, };
    int n, num_apple, idx_apple_x,idx_apple_y, l, l_time, time=1, dir_idx=0, exitFlag=0;
    char l_dir;
    deque<pr> q;
    deque<pr>::iterator iter;
    
    scanf("%d",&n);
    scanf("%d",&num_apple);
    for(int i=0;i<num_apple;i++){
        scanf("%d %d",&idx_apple_x,&idx_apple_y);
        apple[i] = make_pair(idx_apple_x,idx_apple_y);
    } 
    scanf("%d",&l);
    for(int i=0;i<l;i++){
        scanf("%d %c",&l_time, &l_dir);
        move[l_time] = l_dir;
    }

    pr now = make_pair(1,1);
    q.push_back(now);

    while(1) {
        now.first += dir[dir_idx].first;
        now.second += dir[dir_idx].second;

        if(now.first <= 0 || now.second <= 0 || now.first > n || now.second > n){
            // 뱀이 벽을 만난 경우
            break;
        } else {
            for(iter = q.begin(); iter != q.end(); iter++) {
                if( (*iter).first == now.first && (*iter).second == now.second ){
                    // 뱀이 자기 자신을 만난 경우
                    exitFlag = 1; 
                    break;
                }
            }
            if(exitFlag) break;
        }
        int isApple = 0;
        // 이미 먹은 사과인지 판별하기 위한 변수.
        for(int i=0;i<=num_apple;i++) {
            if(now.first == apple[i].first && now.second == apple[i].second) {
                isApple=1;
                apple[i].first = -100;
                apple[i].second = -100;
                // 먹은 사과는 치워버린다.
            }     
        }
        if(!isApple) q.pop_back(); // 사과가 없으니 꼬리도 같이 전진
        
        q.push_front(now); // 머리 전진 

        if(move[time]){
            // 방향을 전환하는 시간인지 판별. 사용자가 입력한 인덱스 외에는 모두 0 이므로 조건문 통과 불가
            if(move[time] == 'D') dir_idx = ++dir_idx%4;
            else if(move[time] == 'L') dir_idx = (dir_idx+3)%4;
        } 
        time++;
    }
    printf("%d",time);
    return 0;
}

 

* 첫 포스트입니다. 하하 

* 코드에 대한 피드백은 언제나 환영합니다.