[백준/C++] 3190 뱀

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

 

코드

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

#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);
#define MAX 101
typedef pair<int, char> dir;
typedef pair<int, int> pi;

int n, k, l, ans = 1, arr[MAX][MAX], dirCnt, nowDir, x, y;

bool isMeet() {
	if (nowDir == 0) {
		x++;
		if (x == n) return true;
	}
	else if (nowDir == 1) {
		y++;
		if (y == n) return true;
	}
	else if (nowDir == 2) {
		x--;
		if (x == -1) return true;
	}
	else {
		y--;
		if (y == -1) return true;
	}

	if (arr[y][x] == 2) return true;
	else return false;
}

int main() {
	FASTIO;

	cin >> n >> k;
	for (int i = 0, y, x; i < k; i++) {
		cin >> y >> x;
		arr[y - 1][x - 1] = 1;
	}
	arr[0][0] = 2;
	deque<pi> q;
	q.push_front({ 0, 0 }); 

	cin >> l;
	vector<dir> d(l);
	for (int i = 0; i < l; i++) cin >> d[i].first >> d[i].second;

	while (true) {
		bool meet = isMeet();
		if (meet) break;

		q.push_front({ y,x });

		if (arr[y][x] == 0) {
			pi tail = q.back();
			q.pop_back();

			arr[tail.first][tail.second] = 0; 
		}
		arr[y][x] = 2;
		ans++;

		if (dirCnt < d.size() && d[dirCnt].first + 1 == ans) {
			if (d[dirCnt].second == 'D') nowDir = (nowDir + 1) % 4;
			else {
				nowDir--;
				if (nowDir < 0) nowDir += 4;
			}
			dirCnt++;
		}
	}

	cout << ans;
	return 0;
}

 

설명

보드의 크기, 사과의 위치를 입력받아 저장합니다. 이때 사과를 1로 보드에 미리 표시해주었습니다. (보드에 저장된 0은 빈 공간, 1은 사과, 2는 뱀을 뜻합니다.)  뱀의 방향 변환 정보는 dir 타입으로 저장합니다. 

 

이후 while문을 돌면서 뱀을 이동시킵니다. isMeet은 뱀이 이동했을 때 벽이나 본인의 몸과 부딪히는지 확인하는 함수입니다. 초반부 if문~else문은 뱀의 현재 이동 방향으로 이동 시 벽과 부딪히는지 확인하는 것이며, 마지막 부분은 본인과 부딪히는지 확인하는 부분입니다. 이 함수의 반환값이 true이면 while문을 종료하고 ans(=게임이 끝나는 초)를 출력합니다.

 

뱀이 성공적으로 이동했다면, 머리 좌표를 덱의 front에 넣어줍니다. 현재 덱의 front에는 머리 좌표, back에는 꼬리좌표가 저장되어 있습니다. 이제 이동한 좌표에 사과가 있는지 확인합니다. 0이라면 빈 공간으로 사과가 없으니 꼬리를 비워야 합니다. 덱의 back에 저장된 좌표를 tail 변수에 담고 pop_back 후 해당 좌표의 값을 2에서 0으로 바꿔줍니다. 머리 좌표의 값을 2로 바꾸고 초를 증가시킵니다. 이후 뱀이 방향 전환을 하는 타이밍이라면 방향을 적절히 변경합니다.  

 

느낀 점

덱을 활용한 구현 자체는 어렵지 않았습니다. 다만, 벽에 닿는다는 개념이 벽에 머리를 둔 상태에서 벽을 향해 이동하려고 할 때라는 뜻인데, 잘못 이해해서 첫 구현에서 답이 다르게 나왔습니다. 직접 배열을 출력해보면서 문제를 찾고 수정해주었는데, 이제는 out of bound 에러가 예제 실행 시 발생했습니다. 확인해보니 dirCnt < d.size() 이 부분에 실수로 등호가 들어가면서 생긴 문제임을 바로 찾아서 고쳐주니 한 번에 맞았습니다!