[BAEKJOON] 3190번 뱀

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

3190번: 뱀

문제조건

 

1. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
2. 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
3. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
4. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

접근방법

먼저 자료구조 queue가 떠올랐다.

사과가 없다면 꼬리부분을 계속삭제해야하므로, 큐에서 맨앞부분은 꼬리 부분이 될것이라고 생각해서 그랬다.

 

근데 문제가 있다. 뱀의 머리부분은 queue 맨뒤에 들어오게 되는데, 큐를 사용하게 된다면, 머리 부분을 계속 갱신해서 다음 탐색할 좌표를 찾아야하는데, 그걸 못한다.

deque

 

쉽게 생각해서 stack과 queue의 결합된 자료구조라고 보면 된다.

덱의 front, back 두 부분다 조회, 삽입, 삭제가 가능하다.

이 문제랑 찰떡인 자료구조이다. 

 

한가지 더 조심해야할 점은, 맵을 탐색할때, dy, dx에 대해서 잘 설정해줘야한다는것이다.

우리가 일반적으로 맵을 탐색할때

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

이런식으로 놓고 풀게 되는데, 이 문제는 방향전환이 있기 때문에 dy,dx 배열안의 값의 순서를 잘 고려해줘야한다!

• 'L' (왼쪽 방향전환), 'D' (오른쪽 방향전환)

왼쪽으로 방향전환을 한다는말은, dy, dx에서 한칸씩 앞으로 당긴다는 의미와 같다.

그래서 나는 dy,dx를 시계방향순서대로 90도씩 오른쪽으로 회전하게 만들어 놨으므로, 방향전환에 대한 식은 dir = (dir+3) %4이다.

오른쪽 방향 전환도 마찬가지로 구할 수 있다.

 

소스코드

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

int n, k, map[101][101], snake[101][101];
char second[10001];
int dy[] = { 1, 0 , -1, 0 };
int dx[] = { 0, -1, 0, 1 };


//게임이 몇 초에 끝나는지(벽 or 자기자신 몸과 부딪히는 경우)
//뱀 위치 (1,1) -> 방향		사과 먹으면 뱀 길이 늘어남(머리만 늘어남)
int main(){
	cin >> n >> k;
	for (int i = 1; i <= k; i++) {
		int row, col;
		cin >> row >> col;
		//사과 위치 입력
		map[row][col] = 1;
	}
	int l;
	cin >> l;
	for (int i = 1; i <= l; i++) {
		int x;
		char c;
		//x초뒤에 방향전환 'L' = 왼쪽, 'D' = 오른쪽
		cin >> x >> c;
		second[x] = c;
	}
	int res = 0;
	deque<pair<int, int> > dq;
	dq.push_back({ 1,1 });
	snake[1][1] = 1;
	//처음 -> 오른쪽 방향
	int dir = 3;
	while (1) {
		res++;
		int y = dq.back().first;
		int x = dq.back().second;
		int ny = y + dy[dir];
		int nx = x + dx[dir];
		//맵 밖으로 나가거나, 자신의 몸에 부딪히면 종료
		if (ny > n || ny <= 0 || nx > n || nx <= 0 || snake[ny][nx]) break;	
		//사과를 먹지 않으면 q의 맨앞부분(꼬리)를 지운다.
		if (!map[ny][nx]) {
			snake[dq.front().first][dq.front().second] = 0;
			dq.pop_front();
		}
		snake[ny][nx] = 1;
		dq.push_back({ ny, nx });
		map[ny][nx] = 0;
		//왼쪽 90도
		if (second[res] == 'L') dir = (dir + 3) % 4;
		else if (second[res] == 'D') dir = (dir + 1) % 4;
	}
	cout << res;
}

 

평소 잘 써보지 않았던 덱을 활용한 구현 문제 였다.

정답률에 비해서 좀 쉽지 않았나 생각되는 문제다.