[백준] 3190번 뱀

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

3190번: 뱀

#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, k, l; //n은 보드의 크기, k는 사과의 개수, l은 방향 변환 횟수
	cin >> n >> k;
	vector<vector<int>> v(n, vector<int>(n));
	int row, col;
	for (int i = 0; i < k; i++) {
		cin >> row >> col;
		v[row - 1][col - 1] = 1; //사과는 1 몸은 2
	}
	cin >> l;
	int second;
	char c;
	queue <pair<int, char>> q;
	for (int i = 0; i < l; i++) {
		cin >> second >> c;
		if (c == 'D') {
			q.push(make_pair(second, 'r')); //오른쪽
		}
		else {
			q.push(make_pair(second, 'l')); //왼쪽
		}
	}
	v[0][0] = 2;
	int index = 0;
	row = 0;
	col = 0;
	char direction[4] = { 'e', 's', 'w', 'n' }; //동, 남, 서, 북
	second = 0;
	/*cout << second << "초" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;*/
	queue<pair<int, int>> tailQueue;
	tailQueue.push(make_pair(0, 0));
	while (true) {
		second++;
		if (!q.empty() && q.front().first + 1 == second) {
			pair<int, char> p = q.front();
			q.pop();
			if (p.second == 'r') {
				index = (index + 1) % 4;
			}
			else {
				index = (index - 1 + 4) % 4;
			}

		}
		if (direction[index] == 'e') {
			if (col + 1 >= n) {
				break;
			}
			col++;
			if (v[row][col] == 2) { //자기 자신이랑 박으면
				break;
			}
			if (v[row][col] == 1) { //사과가 있으면
				v[row][col] = 2;
				tailQueue.push(make_pair(row, col));
			}
			else { //사과가 없으면
				v[row][col] = 2;
				tailQueue.push(make_pair(row, col));
				pair<int, int> tail = tailQueue.front();
				tailQueue.pop();
				v[tail.first][tail.second] = 0;
			}
		}
		else if (direction[index] == 's') { //남쪽
			if (row + 1 >= n) {
				break;
			}
			row++;
			if (v[row][col] == 2) {
				break;
			}
			if (v[row][col] == 1) { //사과가 있으면
				v[row][col] = 2;
				tailQueue.push(make_pair(row, col));
			}
			else { //사과가 없으면
				v[row][col] = 2;
				tailQueue.push(make_pair(row, col));
				pair<int, int> tail = tailQueue.front();
				tailQueue.pop();
				v[tail.first][tail.second] = 0;
			}
		}
		else if (direction[index] == 'w') {
			if (col - 1 < 0) {
				break;
			}
			col--;
			if (v[row][col] == 2) { //자기자신과 부딪히면
				break;
			}
			if (v[row][col] == 1) { //사과가 있으면
				v[row][col] = 2;
				tailQueue.push(make_pair(row, col));
			}
			else { //사과가 없으면
				v[row][col] = 2;
				tailQueue.push(make_pair(row, col));
				pair<int, int> tail = tailQueue.front();
				tailQueue.pop();
				v[tail.first][tail.second] = 0;
			}
		}
		else if (direction[index] == 'n') {
			if (row - 1 < 0) {
				break;
			}
			row--;
			if (v[row][col] == 2) { //자기자신과 부딪히면
				break;
			}
			if (v[row][col] == 1) { //사과가 있으면
				v[row][col] = 2;
				tailQueue.push(make_pair(row, col));
			}
			else { //사과가 없으면
				v[row][col] = 2;
				tailQueue.push(make_pair(row, col));
				pair<int, int> tail = tailQueue.front();
				tailQueue.pop();
				v[tail.first][tail.second] = 0;
			}
		}
		/*cout << second << "초" << endl;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cout << v[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;*/
	}
	cout << second;
	return 0;
}

시작으로부터 x초라는 것을 몰라서 계속 정답과 같거나 정답과 1만큼 차이나서 애를 먹었다.

그러니까 초기에는 즉, 0초에는 1행 1열에 있고 시작으로부터 1초 후인 1초 시점에 머리는 1행 2열에 있다는 것이다.

이걸 아래 글을 읽고서야 알게 되었다.

https://www.acmicpc.net/board/view/13898

글 읽기 - 같은걸로 고민하시는 분 있을까봐 올립니다.

 

코드 설명을 하자면 몇

초에 어느 방향으로 회전할지는 q라는 이름의 큐에 (몇 초, 어느 방향)의 쌍으로 묶어서 담았다.

꼬리를 삭제할 때 꼬리의 위치도 필요하기 때문에 tailQueue라는 것도 만들었다. 한 칸 앞으로 갈 때마다 방문하는 위치를 tailQueue에 (행, 열) 쌍으로 묶어서 집어넣었고 한 칸 앞으로 당길 때마다 tailQueue에서 빼서 그 위치는 0으로 만들어주었다.

사과의 위치는 1로 표시했고 뱀의 위치는 2로 표시했다. 사과는 한 번 먹으면 없어지니까 뱀이 지나간 자리는 0으로 만들어주었다.