[백준][3190] 뱀

이 포스트는 백준 사이트의 뱀 문제 풀이입니다.

문제

해결 과정

문제의 설명처럼 1칸 크기의 뱀이 이동하면서 사과를 먹으면 길어지고
벽 혹은 길어진 자기 자신에게 부딪혔을 때, 시간을 구하는 문제입니다.

따라서 1초간 뱀의 행동을 정리하면 다음과 같습니다.

1. 몸의 길이를 늘려 머리 를 다음 칸에 위치 시킨다.
2. 벽 혹은 자기 자신에게 부딪히는지 확인한다.
3. 늘어난 머리로 사과를 먹은 경우, 5번으로 간다.
4. 늘어난 머리로 사과를 못 먹은 경우, 꼬리를 1칸 없애고 5번으로 간다.
5. 주어진 회전 명령이 있는지 확인하고 있다면 회전한다.

위 과정을 전부 통과하면 1초가 흐르게 됩니다.
따라서 위 과정을 순서대로 수행하여 게임 진행 시간을 알 수 있습니다.

코드 구현

이 문제의 핵심은 뱀의 길이가 늘어남에 따라 뱀이 위치하고 있는 곳을 어떻게 확인할지 입니다.
따라서 저는 이 문제를 해결하고자 list 자료구조를 사용해보았습니다.

뱀의 길이가 머리에서 늘어나고 꼬리에서 제거되기 때문에 Queue 의 push 와 front, pop 연산으로
구현할 수 있지만, 뱀의 머리가 자기 자신과 부딪히는지 확인하는 연산에서
Queue 는 list 와 다르게 for 문을 직접 사용할 수 없으므로 list 를 사용하였습니다.

#include <iostream>
#include <list>

using namespace std;

int N;
struct POINT {
	int row, col;
};
struct DIRECTION {
	int x;
	char c;
};

int dir_row[4]{-1, 0, 1, 0};
int dir_col[4]{0, 1, 0, -1};
list<POINT> snake;
int snake_dir = 1;

void input(int& K, list<POINT>& apples, int& L, list<DIRECTION>& dirs);
bool check_front_block(int new_row, int new_col);
bool eat_apple(int K, list<POINT>& apples, int new_row, int new_col);

int main() {
	int K, L;
	list<POINT> apples;
	list<DIRECTION> dirs;
	input(K, apples, L, dirs);

	snake.push_front({1, 1});

	int run_time = 1;
	while(true) {
		int new_row = snake.front().row + dir_row[snake_dir];
		int new_col = snake.front().col + dir_col[snake_dir];

		if(false == check_front_block(new_row, new_col)) {
			break;
		}

		snake.push_front({new_row, new_col});
		if(false == eat_apple(K, apples, new_row, new_col)) {
			snake.pop_back();
		}

		if(false == dirs.empty() && dirs.front().x == run_time) {
			snake_dir = (dirs.front().c == 'L' ? (snake_dir + 3) % 4 : (snake_dir + 1) % 4);
			dirs.pop_front();
		}

		++run_time;
	}
	cout << run_time;
	return 0;
}

void input(int& K, list<POINT>& apples, int& L, list<DIRECTION>& dirs) {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	cin >> K;
	int row, col;
	for(int i = 0; i < K; ++i) {
		cin >> row >> col;
		apples.push_back({row, col});
	}

	cin >> L;
	int x;
	char c;
	for(int i = 0; i < L; ++i) {
		cin >> x >> c;
		dirs.push_back({x, c});
	}
}

bool check_front_block(int new_row, int new_col) {
	if(new_row <= 0 || new_row > N || new_col <= 0 || new_col > N) {
		return false;
	}

	for(auto p : snake) {
		if(new_row == p.row && new_col == p.col) {
			return false;
		}
	}

	return true;
}

bool eat_apple(int K, list<POINT>& apples, int new_row, int new_col) {
	for(auto it = apples.begin(); it != apples.end(); ++it) {
		if(new_row == it->row && new_col == it->col) {
			apples.erase(it);
			return true;
		}
	}
	return false;
}

실행 결과