[Algorithm][C++] BOJ 3190 뱀

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

3190번: 뱀

 

풀이 핵심

1. stack + queue 기능을 할 수 있는 자료 구조 구현

• stack의 top 기능을 통해 현재 뱀의 머리를 알 수 있어야 한다.
• pop 기능은 꼬리를 잘라내야한다 (queue의 pop)

 

2. 방향을 변경할 때 다음과 같이 나머지 연산을 이용한다.

if (DIR[time] != 0) { // 현재 시간에 방향을 변경해야 할 경우
  if (DIR[time] == 'L') { // 반 시계 방향으로 방향을 변경할 경우
  	dir = (dir + 3) % 4;
  }
  else dir = (dir + 1) % 4; // 시계 방향으로 방향을 변경할 경우
}

 

3. 사과를 먹었을 때는 pop을 생략하고 (꼬리 자르기 생략), 사과를 먹지 못했을 때는 pop을 해준다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int N;
int map[101][101];
int K, L;
char DIR[10001];
struct pos { int r, c; };
pos snake[100 * 100];
int end, start;
void push(int r, int c) {
	map[r][c] = -1;
	snake[start].r = r, snake[start++].c = c;
}
pos top() { return snake[start - 1]; }
void pop() {
	map[snake[end].r][snake[end++].c] = 0;
}

const int dr[] = { 0,1,0,-1 };
const int dc[] = { 1,0,-1,0 };

int Dummy() {
	int time = 0, dir = 0;
	push(1, 1);
	while (1) {
		if (DIR[time] != 0) {
			if (DIR[time] == 'L') {
				dir = (dir + 3) % 4;
			}
			else dir = (dir + 1) % 4;
		}
		++time;
		pos cur = top();
		int nr = cur.r + dr[dir], nc = cur.c + dc[dir];
		if (nr < 1 || nr > N || nc < 1 || nc > N) {
			break;
		}
		if (map[nr][nc] == -1) break;
		if (map[nr][nc] == 1) {
			push(nr, nc);
		}
		else {
			push(nr, nc);
			pop();
		}
	}
	return time;
}

int main() {
	int ret = 0;
	scanf("%d", &N);
	scanf("%d", &K);
	for (int i = 0; i < K; i++) {
		int r, c;
		scanf("%d %d", &r, &c);
		map[r][c] = 1;
	}
	scanf("%d", &L);
	for (int i = 0; i < L; i++) {
		int t;
		char c;
		scanf("%d %c", &t, &c);
		DIR[t] = c;
	}
	ret = Dummy();
	printf("%d", ret);
	return 0;
}

 

아쉬운 점

1. 전형적인 시뮬레이션 / 구현 문제로 어렵지 않게 풀 수 있었다.

2. STL 사용에 익숙해져 있어 deque를 사용하려 했으나 어렵지 않게 구현할 수 있는 자료구조여서 직접 구현했다.

3. 딱히 아쉬운 점이 없는 문제였다.