[백준] #3190번 뱀 (C++)

문제

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

풀이

문제를 푸는데 있어 어렵진 않았지만 생각할게 좀 많았던 문제였다..
푸는 시간만 1시간을 넘겼는데 도저히 암산이 안되서 그림을 그려가면서 푸니 시간이 좀걸렸던 것 같다.

뱀의 머리를 이동한다는 것과 꼬리를 자르는 부분에서 덱을 사용하면 되겠다는 힌트를 얻었고, 그 외 문제에 주어진 조건 처리만 해주면 큰 어려움 없이 풀리는 문제이다.

다만, 예제 3번에서 혼동이 왔었는데.. 아래 그림은 예제 3번에서 뱀이 자기 몸뚱아리를 박는 마지막 모습이다.

처음에는 아직 자기 몸에 닿지 않았는데 게임이 왜끝나지?? 했는데 알고보니 문제의 조건에서 먼저 머리를 다음칸에 위치시킨다라고 언급되어있다.

즉, 머리가 먼저 나간 후에 꼬리 자르기를 실행시켜 결국 위 그림에서 게임이 끝나게된다~~

코드

#include<iostream>
#include<deque>
#include<stdlib.h>
using namespace std;

deque<pair<int, int>> dq;
int n, k, t = 0, d;
int map[101][101];
char changeDir[10001];

// 오, 아래, 왼, 위
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };

bool rangeChk(int x, int y) {
	if (x >= 1 && y >= 1 && x <= n && y <= n) return true;
	return false;
}

bool suicide(int x, int y) {
	deque<pair<int, int>>::iterator it = dq.begin();

	while (it != dq.end()) {
		pair<int, int> p = *it++;

		if (x == p.first && y == p.second) return true;
	}
	return false;
}

int main() {
	cin >> n >> k;

	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
	}

	int l;
	cin >> l;

	for (int i = 0; i < l; i++) {
		int time;
		char d;
		cin >> time >> d;
		changeDir[time] = d;
	}

	dq.push_back({ 1, 1 });

	bool range = false;
	bool s = false;
	while (1) {
		if (range || s) break;
		

		// 방향 전환 가능?
		if (changeDir[t] == 'D') {
			d++;
			if (d == 4) d = 0;
		}
		else if (changeDir[t] == 'L') {
			d--;
			if (d == -1) d = 3;
		}
		// 현재 머리 위치
		int cx = dq.back().first;
		int cy = dq.back().second;

		// 머리 이동
		int nx = cx + dx[d];
		int ny = cy + dy[d];

		// 뱀대갈이 자기 몸뚱아리에 맞는지 && 뱀대갈이 범위를 벗어나는지?
		if (!rangeChk(nx, ny)) range = true;
		if (suicide(nx, ny)) s = true;;

		dq.push_back({ nx, ny });

		// 현재 머리에 사과가 없으면 꼬리 제거
		if (map[nx][ny] == 0) {
			dq.pop_front();
		}
		else {
			map[nx][ny] = 0;
		}

		// 시간 +1
		t++;
	}
	cout << t;
}