[백준] 3190번: 뱀

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

3190번: 뱀

문제가 길고 난해하다.

구현을 위해서는 조건을 세세하게 잘 읽어봐야 한다.

 

1. 뱀 머리를 늘린 후 꼬리 줄이기

2. 보드 행열의 인덱스는 1~N까지

3. 0초에 뱀 머리가 (1, 1)에 위치해 있으며, 1초에 (1, 2), .... 로 변함

4. 방향 전환은 X초가 끝난 뒤, X-1초가 시작하기 전에

 

이정도로 정리하면 도움이 많이 될 것 같다.

 

뱀의 각 마디의 행열 정보는 pair를 이용해서 저장했으며, 전체 뱀은 deque를 이용해서 구현했다(머리와 꼬리에서만 연산이 일어나므로)

보드 위 뱀과 사과의 위치를 표시하기 위해 matrix를 선언했다. (0: 비어있음, 1: 뱀 있음, 2: 사과 있음)

뱀이 움직이는 방향을 저장하는 direct 변수를 선언했다. (0: 위쪽, 1: 왼쪽, 2: 아래쪽, 3: 오른쪽)

(왼쪽으로 회전할 때에는 direct를 1 증가시키고 오른쪽으로 회전할 때에는 direct를 1 감소시키면 된다.)

한칸 움직임이 끝났으면 second를 1 증가시킨다.

 

move()는 뱀을 한칸씩 움직이도록 하는 함수이며, 뱀이 정상적으로 움직였으면 true, 벽이나 자기 자신과 부딪혔으면 false를 반환한다. move()가 false가 될 때까지 실행한 뒤, second를 반환하면 끝!

 

#include <iostream>
#include <deque>
#include <utility>

using namespace std;

deque<pair<int, int>> snake;
int N, K, L;
deque<pair<int, char>> X;
int direct = 3;
int matrix[101][101];    // 0: 비어있음, 1: 뱀 있음, 2: 사과 있음
int sec = 0;

bool move() {
	// move 성공하면 true 반환, 실패하면 false 반환
	sec++;

	int row = snake.back().first;
	int col = snake.back().second;
	
	switch (direct) {
	case 0:
		row--; break;
	case 1:
		col--; break;
	case 2:
		row++; break;
	case 3:
		col++; break;
	}

	snake.push_back(make_pair(row, col));

	//벽에 부딪힌 경우
	if (row < 1 || row > N || col < 1 || col > N) return false;
	// 자기자신과 부딪힌 경우
	if (matrix[row][col] == 1) return false;

	// 사과 먹은 경우
	if (matrix[row][col] == 2) {
		matrix[row][col] = 1;
	}
	// 칸이 비어있는 경우
	else if (matrix[row][col] == 0) {
		matrix[row][col] = 1;
		auto front = snake.front();
		matrix[front.first][front.second] = 0;
		snake.pop_front();
	}

	// 방향 바꿔주는지 검사
	if (!X.empty() && X.front().first == sec) {
		if (X.front().second == 'L')  direct = (direct + 1) % 4;
		else if (X.front().second == 'D')  direct = (direct - 1 + 4) % 4;

		X.pop_front();
	}

	return true;
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < K; i++) {
		int row, col;
		cin >> row >> col;
		matrix[row][col] = 2;
	}

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

	snake.push_back(make_pair(1, 1));
	matrix[1][1] = 1;

	while (move());
	cout << sec;
}

여담으로 vector, list, deque로 각각 구현했는데 아무런 차이가 없었다.