[백준 3190번 - 뱀] C++ 풀이

백준 3190번.

N x N 정사각 보드가 있고, 초기 상태의 뱀의 위치는 (0,0), 몸길이는 1이다. (보드 한칸 = 몸길이 1)

주어진 방향대로 1초에 한 칸만큼 이동한다. 

만약 그 칸에 사과가 있으면 먹고, 꼬리는 그대로 둔 채 머리만 이동한다. (즉, 몸 길이가 늘어난다.)

만약 그 칸에 사과가 없으면, 머리와 꼬리가 같이 이동한다. (즉, 몸 길이는 그대로다.)

 

사용한 알고리즘은 다음과 같다.

•  deque
• 시뮬레이션

 

간략한 설명

뱀의 몸이 있는 위치를 저장하기 위해서 deque 를 하나 두었다.

deque 는 앞/뒤 양방향으로 push/pop이 가능하기 때문에 뱀의 길이와 머리, 꼬리 위치가 변함에 따라 좌표 저장이 용이할 것이라는 생각이 들었다.

사과의 위치를 저장하기 위한 map, 뱀의 몸이 위치해 있는 곳을 체크하기 위해서 check 배열도 만들었다.

 

게임이 끝날 때까지 아래를 반복한다.

현재 위치 좌표값 계산

1. 현재 위치가 범위에 벗어났거나 (벽에 부딪힘) / 뱀의 몸이 위치한 곳이라면 break

현재 위치 deque 앞에 넣어준다.

현재 위치 deque 앞에 넣어준다.

2. 현재 위치가 사과가 있는 곳이라면, 

    - map 에서 사과 없애주기

3. 현재 위치가 사과가 없는 곳이라면, 꼬리 위치 이동시켜주기

    - deque 의 제일 뒤에 있는 좌표 값에 해당하는 check 배열 값 = false

    - deque 의 제일 뒤 값 pop

4. 시간 경과에 따라서 D, L 에 따른 이동 방향 반영

 

 

완성된 코드

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

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

deque<pair<int, int>> dq; // 뱀의 몸 표시
int map[101][101] = {0, }; // 사과 위치 표시
vector<pair<int, char>> dir;
bool check[101][101]; // 뱀의 몸이 있는지 여부
int n, k, x, y, l, m;
char c;

int main() {
	cin>>n;
    cin>>k;
    for(int i=0; i<k; i++){
        cin>>x>>y;
        map[x - 1][y - 1] = 1;
    }

    cin>>m;
    for(int i=0; i<m; i++){
        cin >> l >> c;
        dir.push_back(make_pair(l, c));
    }

	int dir_idx = 0;
	int time = 0;
	int cx = 0;
	int cy = 0;
	dq.push_front(make_pair(0, 0));
	check[0][0] = true;
	int idx = 0;
	while(1) {
		time++;
		int nx, ny;
		nx = cx + dx[dir_idx];
		ny = cy + dy[dir_idx];
		if (nx < 0 || ny < 0 || nx >= n || ny >= n || check[nx][ny] == true) {
			break;
		}
		cx = nx;
		cy = ny;
		check[nx][ny] = true;
		dq.push_front(make_pair(nx, ny));
		// 사과가 없다면
		if (map[nx][ny] == 0) {
			int tx = dq.back().first;
			int ty = dq.back().second;
			check[tx][ty] = false;
			dq.pop_back();
		} else { // 사과가 있다면
			map[nx][ny] = 0;
		}

		// 방향 조절
		if(time == dir[idx].first) {
			if (dir[idx].second == 'D') {
				dir_idx++;
				if (dir_idx > 3)
					dir_idx = 0;
			} else {
				dir_idx--;
				if (dir_idx < 0)
					dir_idx = 3;
			}
			idx++;
		}
	}
	cout << time << endl;

	return 0;
}