[C++] 백준 3190번 : 뱀

문제

 

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

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

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

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

 

입력

 

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데,  정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

 

출력

 

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

 

풀이

 

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int board[105][105];
int i;
char dir[4] = {'E','N','W','S'};
int dir_xy[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
 
int main(){
    int N;
    scanf("%d",&N);
 
    int apple_num;
    scanf("%d",&apple_num);
 
    for(i=0;i<apple_num;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        board[y-1][x-1]=2;
    }    
 
    int rotate_cnt;
    queue<pair<int, char> > rotate;
    scanf("%d",&rotate_cnt);
 
    for(i=0;i<rotate_cnt;i++){
        int X;
        char C;
        scanf("%d %c",&X,&C);
        rotate.push({X,C});
    }
 
    int time = 0;
    int cur_x = 0;
    int cur_y = 0;
    int cur_dir = 0;
 
    queue<pair<int, int> > snake;
    board[0][0] = 1;
    snake.push({0,0});
 
    int rotate_time = rotate.front().first;
    int rotate_dir = rotate.front().second;
    rotate.pop();
 
    while(1){
        time++;
 
        int next_x = cur_x + dir_xy[cur_dir][0];
        int next_y = cur_y + dir_xy[cur_dir][1];
 
        if(next_x<0 || next_x>=N || next_y <0 || next_y >= N || board[next_x][next_y]==1){ // wall or snake's body
            printf("%d\n",time);
            return 0;
        }
        
       
        if(board[next_x][next_y]!=2){ // not apple
            int del_x = snake.front().first;
            int del_y = snake.front().second;
            snake.pop();
            board[del_x][del_y] = 0;
        }
 
        snake.push({next_x,next_y});
        board[next_x][next_y] = 1;
 
        cur_x = next_x;
        cur_y = next_y;
 
        if(time==rotate_time){
            if(rotate_dir == 'L') cur_dir = (cur_dir + 1)%4;
            else if(rotate_dir == 'D') cur_dir = (cur_dir + 3)%4;
            
            if(!rotate.empty()){
                rotate_time = rotate.front().first;
                rotate_dir = rotate.front().second;
                rotate.pop();
            }
        }
    }
}

 

삼성 SW 역량 테스트 기출 문제!

요즘 삼성 소프트웨어 기출 문제를 풀고 있는데 다 코드가 길게 나온다ㅠㅠ

먼저 보드의 크기와 사과의 개수를 입력받고 사과의 위치또한 입력 받는다

입력 받은 사과의 위치를 보드에 체크해주었다

0을 기준으로 보드를 사용했는데 그냥 1부터 할 걸 그랬다

 

다음은 queue를 사용해서 뱀의 이동에 관련된 정보를 저장해주었다

큐가 아니라 벡터나 int,char 배열 두개에 integer 하나를 index로 사용해도 무방할듯하다

 

모든 정보를 입력받고 나서는 뱀을 움직이게 해주었다

snake queue는 뱀이 board의 어느어느 좌표에 있는지를 나타내어준다

뱀이 이동하면 꼬리부분이 사라지니까 pop을 해주고 머리부분은 push를 해준다

이때 사과를 먹으면 뱀의 길이가 길어지니까 pop은 해주지 않고 머리부분만 push 해주었다

pop 해 줄 때 board의 뱀 위치도 다시 0으로 초기화해준다

 

이동은 뱀이 보고 있는 방향이 어디인지에 따라 달라진다

동서남북으로 direction을 저장해주고 direction별로 다음번 이동 위치를 쉽게 사용하기 위해 dir_xy에 저장해주었다

뱀이 회전할 시간이 되면 원래 방향에서 오른쪽,왼쪽으로 회전하는 것을 dir 배열의 순서를 이용하여 구현해주었다

 

신경써주어야 할 것들이 많아 코드가 길어졌지만 난이도는 별로 어렵지 않았다