백준 3190번 문제 뱀 C/C++ 풀이

시뮬레이션류 문제는 푸는게 머리 아프다.

문제에 있는 내용들을 그대로 코드로 구현해야하는데,

어떤 자료구조가 좋을지 결정해야한다.

 

사실 아는거라고 해봤자 배열밖에 없었는데,

이번 문제는 Deque(덱)을 이용하면 쉽게 풀 수 있는 문제였다.

(배열을 이용한 괴상한 풀이도 적어놓을 예정,..,,)

 

덱을 알기 위해서는 큐를 먼저 알아야 한다.

 

Queue(큐)란?

 

먼저 넣은 데이터가 먼저 나오는 선입선출(First-In, First-Out, FIFO) 구조이다. 후입선출(Last-In, First-Out, LIFO)를 가진 stack과는 반대되는 개념이다. 줄 서서 먹는 식당으로 생각하면 될 것 같다. 줄을 기다릴 때 온 순서대로 사람들이 차곡차곡 쌓이고 맨 먼저 온 사람부터 식당에 들어가니까. 시간 순서대로 사람들이 오는 것, 즉 자료를 넣는 것을 'push'라고 하고 먼저 온 사람이 먹으러 식당으로 들어가는 것, 즉 자료가 나가는 것을 'pop'이라고 한다.

 

그러면 Deque(덱)은?

 

Double-ended Queue의 약자로 양쪽 끝에서 모두 삽입과 삭제가 가능한 자료구조를 뜻하게 된다. 뱀 문제의 경우 머리와 꼬리가 삭제될 때도 있고 새로 추가될 때도 있는데 덱을 사용하면 이를 관리하기가 용이하다.

 

 

해당 문제를 배열로 푼다면..?

 

#include <stdio.h>

//input이 긴 문제는 일일히 input 치기가 귀찮아서 fopen으로 input을 넣는다.
FILE* in = fopen("input.txt", "r");

int n;
int k;
int l;
int input_array[101][101];
char input_dir[10001];
int dir_x[4] = { 0, 1, 0, -1 };
int dir_y[4] = { 1, 0, -1, 0 };
int  head_dir_x, head_dir_y, tail_dir_x, tail_dir_y, head_x, head_y, tail_x, tail_y;
int time_delay;
bool possible = true;
int time;
int tmp_dir_x, tmp_dir_y;

void turn(int time) {
	//다음 head의 방향을 판단
	if (input_dir[time] == 'D')
	{
		head_dir_x = (head_dir_x + 1) % 4;
		head_dir_y = (head_dir_y + 1) % 4;
	}
	else if (input_dir[time] == 'L')
	{
		head_dir_x = (head_dir_x + 3) % 4;
		head_dir_y = (head_dir_y + 3) % 4;
	}

	//head 위치 갱신
	head_x = head_x + dir_x[head_dir_x];
	head_y = head_y + dir_y[head_dir_y];

	//tail의 경우 사과를 먹으면 방향이 바뀌지 않을 수 있기 때문에 tmp로 tail의 방향을 저장해둔다.
	tmp_dir_x = tail_dir_x;
	tmp_dir_y = tail_dir_y;

	//다음 tail의 방향을 판단
	if (input_dir[time - time_delay] == 'D')
	{
		tail_dir_x = (tail_dir_x + 1) % 4;
		tail_dir_y = (tail_dir_y + 1) % 4;
	}
	else if (input_dir[time - time_delay] == 'L')
	{
		tail_dir_x = (tail_dir_x + 3) % 4;
		tail_dir_y = (tail_dir_y + 3) % 4;
	}

	//다음 head의 위치에 따른 움직임
    //head 위치에 아무것도 없다면,
	if (input_array[head_x][head_y] == 0)
	{
    	//head에 뱀이 있다는 것을 표시
		input_array[head_x][head_y] = 1;
        //기존 tail은 위치 삭제
		input_array[tail_x][tail_y] = 0;
        //tail 위치 갱신
		tail_x = tail_x + dir_x[tail_dir_x];
		tail_y = tail_y + dir_y[tail_dir_y];
	}
    //head 위치에 사과가 있다면
	else if (input_array[head_x][head_y] == 2)
	{
    	//head에 뱀이 있다는 것을 표시
		input_array[head_x][head_y] = 1;
        //tail은 그대로 남고
		input_array[tail_x][tail_y] = 1;
        //head와 tail의 방향 전환이 시간 간격이 1만큼 더 차이나게 됨
		time_delay++;
        //원래의 tail 방향대로 돌려놓기
		tail_dir_x = tmp_dir_x;
		tail_dir_y = tmp_dir_y;
	}
    //head 위치에 뱀의 몸이 있다면
	else if (input_array[head_x][head_y] == 1)
	{
    	//fail
		possible = false;
	}
}

int main() {
	//입력
	fscanf(in, "%d", &n);
	fscanf(in, "%d", &k);
	for (int i = 0; i < k; i++)
	{
		int tmp_x, tmp_y;
		fscanf(in, "%d %d", &tmp_x, &tmp_y);
		input_array[tmp_x - 1][tmp_y - 1] = 2;
	}
	fscanf(in, "%d", &l);
	for (int i = 0; i < l; i++)
	{
		int tmp_s;
		char tmp_dir;
		fscanf(in, "%d %c", &tmp_s, &tmp_dir);
		input_dir[tmp_s] = tmp_dir;
	}
    //불가능할 때까지 반복
	while (1==1)
	{
		turn(time);
        time++;
        //불가능 조건, head가 벽을 벗어나거나 뱀의 몸과 부딪히거나
		if (head_x < 0 || head_x >= n || head_y < 0 || head_y >= n || !possible)
			break;
        //디버깅용 출력
		/*for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
				printf("%d ", input_array[i][j]);
			printf("\n");
		}
		printf("%d\n\n\n", time);*/
	}
    //답 출력
	printf("%d", time);
}

 

이와 같은 더럽고 무지막지한 코드를 얻게 된다...

 

하지만 deque로 풀어본다면?

 

 

#include <cstdio>
#include <utility>
#include <deque>
#include <queue>

using namespace std;

//input이 긴 문제는 일일히 input 치기가 귀찮아서 fopen으로 input을 넣는다.
FILE* in = fopen("input.txt", "r");

int n;
int k;
int l;
//자료구조 특성을 보이고자 시간에 따른 방향 값을 나타내는 dir은 queue로 snake는 deque으로 표시
deque<pair<int, int>> snake;
queue<pair<int, char>> dir;
int input_array[101][101];
int dir_x[4] = { 0, 1, 0, -1 };
int dir_y[4] = { 1, 0, -1, 0 };
int dir_num;
int time = 1;

// 뱀의 다음 방향을 결정
void direction(queue<pair<int, char>>& dir, int time) {
	if (dir.front().first == time - 1)
	{
		if (dir.front().second == 'D')
			dir_num = (dir_num + 1) % 4;
		else if (dir.front().second == 'L')
			dir_num = (dir_num + 3) % 4;
		dir.pop();
	}
}

bool snake_go(deque<pair<int, int>>& snake, queue<pair<int, char>>& dir, int time) {
	//dir queue가 비어있다면 dir.front()에서 오류가 나기 때문에 비어있는지 확인 후 진행
	if(!dir.empty())
		direction(dir, time);
	int tmp_x = snake.back().first + dir_x[dir_num];
	int tmp_y = snake.back().second + dir_y[dir_num];
    //뱀이 벽 밖으로 나간 경우
	if (tmp_x < 0 || tmp_x >= n || tmp_y < 0 || tmp_y >= n)
		return false;
    //뱀이 자신의 몸이랑 부딪히는 경우, deque은 순회 가능!
	for (int i = 0; i < snake.size(); i++)
	{
		if (snake[i].first == tmp_x && snake[i].second == tmp_y)
			return false;
	}
    //모두 해당 안된다면 새로운 뱀 위치 추가
	snake.push_back(make_pair(tmp_x, tmp_y));
    //가려는 위치가 비어 있다면 뱀의 가장 오래된 위치를 삭제
	if (input_array[tmp_x][tmp_y] == 0)
	{
		snake.pop_front();
	}
    //아니라면 사과 먹었으니 빈 곳으로 갱신
	input_array[tmp_x][tmp_y] = 0;
    //다음 시간대로 진행
	return true;
}

int main() {
	//입력
	fscanf(in, "%d", &n);
	fscanf(in, "%d", &k);
	for (int i = 0; i < k; i++)
	{
		int tmp_x, tmp_y;
		fscanf(in, "%d %d", &tmp_x, &tmp_y);
		input_array[tmp_x - 1][tmp_y - 1] = 2;
	}
	fscanf(in, "%d", &l);
	for (int i = 0; i < l; i++)
	{
		int tmp_s;
		char tmp_dir;
		fscanf(in, "%d %c", &tmp_s, &tmp_dir);
		dir.push(make_pair(tmp_s, tmp_dir));
	}
	snake.push_back(make_pair(0, 0));
	//불가능할 때까지 반복
	while (snake_go(snake, dir, time))
	{
		time++;
	}
	printf("%d", time);
}

깔-끔