백준 3190 뱀 c++

해당 문제는 구현문제이다. 몇가지 어려움이 있었다.

1. 테스트케이스 3번

테스트케이스 2번과 테스트케이스 3번이 다른 답을 내는 것은 뱀은 몸을 먼저 늘린 후에 방향 전환을 하기 때문이다. 13초에 뱀이 머리를 늘리면 꼬리와 닿게 되기 때문에 13초에 끝나게 된다.

2. 방향 전환 배열 선언

방향 전환하는 배열을 static하게 dir[101] 이런식으로 세웠었다. 하지만 시간이 101만큼 들어오지 않고 n*n 행렬이라고 할 때 여러번 순환을 한다고 하면 n*n*n .. 으로 계속 들어올 수 있고 이는 세그멘테이션 폴트를 야기할 수 있다. 

따라서 map을 사용했다. vector을 사용할 수 있지만 time n 에 대해 방향 전환을 하는지 쉽게 찾기 위해서는 key와 value를 갖는 map이 나을 것 같다고 판단했다. 따라서 map을 사용해서 key, value를 저장하고 key에 따라 매번 검색했다.

3. dx, dy 관련

왼쪽, 오른쪽으로 회전하는 것에 대해 dx, dy를 다음과 같이 선언했다.

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

그리고 dir = (dir-1)%4, dir = (dir+1)%4 이런식으로 방향 전환을 했는데,

dir = (dir-1)%4에 대해 dir = 0이 되는 순간에 음수가 나올 수 있다는 것을 간과했다. 따라서 dir<0이 되는 순간에 dir = 3으로 바꿔주어 90도 회전이 가능하게 바꿔줬다. 

#include <iostream>
#include <vector>
#include <cstring>
#include <deque>
#include <map>

using namespace std;

int board[101][101];
int N, K, L;
vector<pair<int, int>> apple;

map<int, char> m;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int check(deque<pair<int, int>> d) {
	for (int i = 0;i < d.size();i++) {
		for (int j = i + 1;j < d.size();j++) {
			if (d[i].first == d[j].first && d[i].second == d[j].second) {
				return -1;
			}
		}
	}
	return 1;
}

int move_deque(deque<pair<int, int>>& d1, int dir) {

	int x = d1.front().first;
	int y = d1.front().second;
	x = x + dx[dir] % 4;
	y = y + dy[dir] % 4;
	d1.push_front({ x, y });
	if (check(d1) == -1) {
		return -1;
	}
	if (board[y][x] != 1) {
		d1.pop_back();
	}
	else {
		board[y][x] = 0;
	}
	return 1;
}

int solve(void) {
	int x, y, dir, len, time, bx, by;
	deque<pair<int, int>> d;
	dir = 0, len = 1, time = 0;
	d.push_back({ 0, 0 });
	while (1) {
		x = d.front().first;
		y = d.front().second;
		bx = d.back().first;
		by = d.back().second;
		if (x < 0 || y < 0 || x >= N || y >= N) {
			return time;
		}
		if (bx < 0 || by < 0 || bx >= N || by >= N) {
			return time;
		}
		if (check(d) == -1) {
			return time - 1;
		}
		time++;
		if (move_deque(d, dir) == -1) {
			return time;
		}

		if (m.find(time) == m.end()) {
			continue;
		}
		else {
			if (m.find(time)->second == 'L') {
				dir = (dir - 1) % 4; 
				if (dir < 0) {
					dir = 3;
				}
			}
			else if (m.find(time)->second == 'D') {
				dir = (dir + 1) % 4;
			}
		}
	}
}
int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	memset(board, 0, sizeof(board));
	cin >> N >> K;
	for (int i = 0;i < K;i++) {
		int x, y;
		cin >> y >> x;
		board[y - 1][x - 1] = 1;
	}
	cin >> L;
	for (int i = 0;i < L;i++) {
		int x;
		char y;
		cin >> x >> y;
		m.insert(make_pair(x, y));
	}
	cout << solve() << endl;
	return 0;
}

이렇게 해서 2번 틀리고 세번째에 맞았다.

 

디버깅에 사용한 테스트케이스는 아래와 같다.

8
5
6 1
7 3
3 5
5 7
5 6
12
2 D
8 D
10 D
12 D
18 L
20 L
22 L
24 L
25 L
28 L
32 D
33 L