(백준 3190번 뱀 C++) 라이님 블로그 대회 알고리즘 따라잡기 7) 리스트, 배열, 연결 리스트 4

아직 단순 구현이 익숙하지 않은지라,, 다른 분들의 풀이를 보면서 아이디어를 얻었다.

 

백준 3190번

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

3190번: 뱀

 

(1) 우선 이 문제에서는 크게 3개의 상태를 N*N 맵에 나타내야 한다.

1. 아무것도 없는 상태 = 0

2. 사과가 있는 상태 = 1

3. 뱀이 자리를 차지하고 있는 상태 = 2

 

(2) 뱀의 상태와 움직임을 나타내야 한다.

뱀의 위치를 나타내기 위해 queue에 pair<int, int>를 추가해서 많이 썼다.

- 만약 사과가 있다면 사과 자리를 2로 만들어주고, 사과 좌표를 큐에 push해줬다.

- 만약 사과가 없으면 꼬리를 pop해주고, pop한 좌표는 0로, 새로운 좌표는 push해주는 동시에 2로 만들어주었다.

 

(3) 게임이 끝나는 조건을 추가해야 한다.

- 뱀이 벽에 부딪힐 경우(x,y좌표가 N보다 커지는 경우)

- 뱀의 몸에 부딪힐 경우(map의 원소가 2인 경우)

 

(4) 시간에 따라 방향이 바뀐다는 사실을 고려해야 한다.

dir_idx = 1이라 두고

dy = {-1, 0, 1,0}, dx = {0, 1, 0, -1}로 정의했다.

dir_idx = 1 일 때 (dy[1], dx[1]) = (0, 1)로 위쪽을 나타낸다. 

dir_idx = 2 일 때 (dy[2], dx[2]) = (1, 0)로 오른쪽을 나타낸다.

dir_idx = 0 일 때 (dy[0], dx[0]) = (-1, 0)로 왼쪽을 나타낸다. 

 

즉, dir_idx를 하나 늘리면 오른쪽 회전을, dir_idx를 하나 줄이면 왼쪽 회전을 나타낸다. 

 

방향 정보는 아래 선생님들의 블로그를 참고했다.

1. https://hagisilecoding.tistory.com/82

백준 3190 뱀 c++ [컴공과고씨]

출처 ㅣ&nbsp;https://hagisilecoding.tistory.com/82

2. https://0m1n.tistory.com/99

[BOJ] 백준 3190 뱀 c++ (구현, deque)

특히 2번째 블로그!! 코드가 굉장히 직관적이라서 추천한다.

 

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

constexpr int MAX_N = 101;
int arr[MAX_N][MAX_N] = { 0 };

int main() {
	deque<pair<int, int>> dq;  // 뱀 
	dq.emplace_back(make_pair(1, 1)); arr[1][1] = 1; // 뱀 위치 초기화
	queue<pair<int, int>> q;   // 방향전환
	int dx[4] = {0,1,0,-1,};   // 오른쪽, 아랫쪽, 왼쪽, 윗쪽
	int dy[4] = {1, 0, -1, 0}; // (0, 1), (1, 0), (0, -1), (-1, 0)
	int dir_idx = 0;

	int N, K; cin >> N >> K;
	for (int i = 0; i < K; i++) {
		int x, y; cin >> x >> y;
		arr[x][y] = 2; // 사과 위치
	}
	int L; cin >> L;
	for (int i = 0; i < L; i++) {
		int X; char c; cin >> X >> c;
		q.emplace(make_pair(X, c));
	}

	int time = 0;
	while (1) {
		time++;
		// (x, y) : 뱀의 머리, (row, col) : 뱀이 향할 곳
		int x = dq.front().first; int y = dq.front().second;
		int row = x + dx[dir_idx]; int col = y + dy[dir_idx];
		// 벽이나 자기자신과 부딪힌 경우
		if (row <= 0 || col <= 0 || row > N || col > N || arr[row][col] == 1) break;
		// 사과가 없다면 꼬리를 줄인다 = dq의 back을 pop한다.
		
		if (arr[row][col] != 2) { //사과가 아니라면
			// 뱀이 차지하던 꼬리(1)을 (0)로 수정한다
			arr[dq.back().first][dq.back().second] = 0;
			dq.pop_back();
		}
		// 사과가 있든 없든 일단 뱀이 향하는 곳으로 몸이 늘어남
		arr[row][col] = 1;
		dq.emplace_front(make_pair(row, col));
		
		if (!q.empty()) {
			int rot_time = q.front().first;
			char rot_char = q.front().second;
			if (rot_time == time) {
				if (rot_char == 'L') dir_idx = (dir_idx - 1 + 4) % 4;
				else dir_idx = (dir_idx + 1) % 4;
				q.pop();
			}
		}
	}
	cout << time;
	return 0;
}

 

 

방향 부분이 틀려서 ^^ 덕분에 1시 취침한다.