[C++] BOJ(백준) 3190 뱀

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

3190번: 뱀

 

덱을 이용한 구현문제다.

 

스택을 사용해도 될 것 같다고 생각을 했는데 맨 처음 넣은 원소를 확인하기 힘들고

언제 양방향에 넣고 뺄지 모르니까 덱을 사용했다.

 

헷갈리는 부분이 존재했는데 뱀의 머리를 구하려면 front, 꼬리를 구하려면 back이라고 생각했다.

큐에는 꼬리가 먼저 들어가고 머리가 나중에 추가되는 방식이라 머리가 back, 꼬리가 front였다.

 

뱀의 머리에 대한 위치를 찾고, 방향에 맞추어 r, c 값을 증감시켜 준다.

범위를 벗어나서 벽에 부딪히는지 검사를 하는 것도 방향에 따라 달라진다.

(이 점은 방향 별로 안 나누고 한 번에 4방향 다 검사를 해주는 방법도 괜찮다고 생각한다.)

범위에 적합하다면 좌표를 큐에 넣어주고 그 자리에 사과가 있는지 뱀이 있는지 등을 검사한다.

 

뱀이 뱀을 밟는지 검사하기 위해 어떤 방법을 써야 할지 조금 고민을 했다.

1. 큐에는 뱀의 길이만큼의 좌표만 들어있기 때문에 큐를 검사한다.

-> 뱀의 길이가 얼마나 길어질지 모르는데 다 넣었다 빼면서 검사하는 건 무리다.

 

2. 배열에 표시를 한다.

-> 이 방법을 선택했다. 사과는 1, 뱀은 2로 표현한다.

 

뱀의 머리가 도착한 곳이 1이라면 꼬리는 줄지 않고 0이라면 꼬리는 줄어든다.

0일 때 꼬리가 줄어들기 위해서는 큐에서 pop_front와 동시에 front로 꼬리 좌표를 찾아 배열을 0으로 만든다.

또한 도착한 곳이 2라면 뱀이 뱀을 밟은 것이므로 종료되게 했다.

 

방향을 돌리기 위해서는 시계방향으로 임의의 숫자를 부여하고 오른쪽은 +1 왼쪽은 -1로 계산했다.

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

int dummy[101][101]; // 뱀의 위치와 사과를 나타내기 위함 (사과1, 뱀2)
int snakes[101]; // 뱀이 움직이는 시간 저장
char snaked[100]; // 뱀이 움직이는 방향 저장

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

	int a;	cin >> a;
	for (int i = 0; i < a; i++) {
		int x, y;		cin >> x >> y;
		dummy[x][y] = 1;
	}

	int s;		cin >> s;
	for (int i = 0; i < s; i++) 
		cin >> snakes[i] >> snaked[i];

	// 마지막 방향을 회전하고 앞으로 가야하기 때문에 보드 크기만큼 더해서 마지막에 저장
	snakes[s] = snakes[s - 1] + n;

	deque<pair<int, int>> q;
	q.push_back({ 1, 1 });
	dummy[1][1] = 2;

	int sec = 0;
	int d = 1;
	for (int i = 0; i <= s; i++) {
		for (int j = sec; j < snakes[i]; j++) {
			sec++;
			// 가장 나중에 큐에 삽입 된 원소 즉, 뱀의 머리
			pair<int, int> cur = q.back();

			int r, c;

			// 우
			if (d == 1) {
				r = cur.first;
				c = cur.second + 1;

				if (c > n) {
					cout << sec;
					return 0;
				}
			}

			// 하
			else if (d == 2) {
				r = cur.first + 1;
				c = cur.second;

				if (r > n) {
					cout << sec;
					return 0;
				}
			}

			// 좌
			else if (d == 3) {
				r = cur.first;
				c = cur.second - 1;

				if (c < 1) {
					cout << sec;
					return 0;
				}
			}

			// 상
			else if (d == 4) {
				r = cur.first - 1;
				c = cur.second;

				if (r < 1) {
					cout << sec;
					return 0;
				}
			}

			// 뱀이 벽에 부딪히지 않으면 push
			q.push_back({ r, c });

			// 움직인 자리가 사과라면 뱀의 위치만 저장해줌
			if (dummy[r][c] == 1) dummy[r][c] = 2;

			// 움직인 자리에 아무것도 없다면 뱀의 꼬리 한 칸 제거
			else if (dummy[r][c] == 0) {
				dummy[r][c] = 2;
				pair<int, int> tail = q.front();
				dummy[tail.first][tail.second] = 0;
				q.pop_front();
			}

			// 움직인 자리에 뱀이 있다면 (dummy[r][c] == 2) 종료
			else {
				cout << sec;
				return 0;
			}
		}
		
		// 임의로 방향을 시계방향으로 정했기 때문에 우측은 + 1 좌측은 - 1
		if (snaked[i] == 'L') {
			d--;
			if (d < 1) d = 4;
		}
		else {
			d++;
			if (d > 4) d = 1;
		}
	}
}

 

처음에는 바깥 반복문에서 바로 if를 사용해 방향 1, 2, 3, 4에 따라 반복문을 돌렸다.

제출에 성공하고 보니 동일한 코드가 많아서 방향에 영향을 미치는 부분만 if 문에 넣고 동일한 코드는 한 번만 작성했다.

메모리도 조금 줄고 코드 길이는 거의 2배가 줄었다.