3190 - 뱀 (시뮬레이션)

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

3190번: 뱀

최근 알고리즘 공부의 열기가 식어서... 열을 올리기 위해 쉬운 시뮬레이션 문제를 가져왔습니다.

 

참 신기한게, 1년 전만 하더라도 푸는데 오래 걸렸을 문제인데, 이제는 1시간도 채 안되서 뚝딱 풀어냈네요. 헤헤

 

이래야 재밌지

본 문제의 경우엔 그냥 시키는 대로 짜면 됩니다.

 

문제에서 친히 분기를 설명을 해주었고, (사과가 있을 때, 없을 때) 뱀의 머리가 벽 혹은 자신의 몸인지 아닌지만 한 번 더 분기를 해주면 문제는 쉽게 풀립니다.

 

이 문제의 경우엔 한 가지의 자료구조를 활용해야 하는데, 바로 큐(Queue) 입니다. 머리와 꼬리의 개념을 가지고 선입선출을 하면서 위치가 이동하기 때문에, 큐를 만들어서 사용해야하는데, 처음엔 동적으로 만들어서 하려다가... 굳이 범위가 작은 문제에서까지 하고 싶지 않아서, 그냥 정적으로 범위 잡아서 했습니다.

 

코드를 볼까요?

#include <stdio.h>
#define MAX_QUEUE_LEN 7500

int Queue[MAX_QUEUE_LEN][2], head = 0, tail = 0;
int apple[100][2], direct[10000], dx = 1, dy = 0;
int N, K, L, t = 0, idx;
char dir;

int check() {
	if (Queue[head][0] + dy < 1 || Queue[head][0] + dy > N || Queue[head][1] + dx < 1 || Queue[head][1] + dx > N) return 0;
	for (int i = tail; i <= head; ++i) if (Queue[head][0] + dy == Queue[i][0] && Queue[head][1] + dx == Queue[i][1]) return 0;
	return 1;
}

int appleCheck() {
	for (int k = 0; k < K; ++k) {
		if (apple[k][0] == Queue[head][0] + dy && apple[k][1] == Queue[head][1] + dx) {
			apple[k][0] = -1;
			apple[k][1] = -1;
			return 1;
		}
	}
	return 0;
}

void directCheck() {
	if (direct[t] == 'D') {
		if (dx == 1) dx = 0, dy = 1;
		else if (dy == 1) dx = -1, dy = 0;
		else if (dx == -1) dx = 0, dy = -1;
		else if (dy == -1) dx = 1, dy = 0;
	}
	if (direct[t] == 'L') {
		if (dx == 1) dx = 0, dy = -1;
		else if (dy == -1) dx = -1, dy = 0;
		else if (dx == -1) dx = 0, dy = 1;
		else if (dy == 1) dx = 1, dy = 0;
	}
}

int main(void) {
	scanf("%d", &N);
	scanf("%d", &K);
	for (int k = 0; k < K; ++k) scanf("%d %d", &apple[k][0], &apple[k][1]);
	scanf("%d", &L);
	for (int l = 0; l < L; ++l) {
		scanf("%d %c", &idx, &dir);
		getchar();
		direct[idx] = dir;
	};
	Queue[0][0] = 1; Queue[0][1] = 1; // 행, 열

	while (1) {
		++t;
		if (!check()) break;
		if (appleCheck()) {
			++head;
			Queue[head][0] = Queue[head - 1][0] + dy; Queue[head][1] = Queue[head - 1][1] + dx;
		}
		else {
			++tail;
			++head;
			Queue[head][0] = Queue[head - 1][0] + dy; Queue[head][1] = Queue[head - 1][1] + dx;
		}
		directCheck();
	}
	printf("%d", t);
}

check 함수는 벽과 몸에 부딫히는지 확인하는 것이며, appleCheck는 사과가 있는지 없는지, directCheck는 방향성을 결정하는 함수입니다.

 

아마 다들 쉽게 푸실거라고 생각합니다.

쨘

---

이상 3190 - 뱀 (시뮬레이션) 였습니다. ^_^