[백준] 3190번: 뱀

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

3190번: 뱀

 

문제 이해

그냥 시뮬레이션을 돌려주면 되는 문제인데, 뱀을 정의하는 방법을 조금 생각해내야 한 문제였다.

일종의 C++에서의 덱 처럼 사용할 수 있는 snake라는 배열을 만들어줬다. snake는 현재 snake의 몸이 존재하는 칸들이 순서대로 담긴다.

사과의 위치는 좌표로 받기 때문에, 받아서 바로 맵에 1로 표시해준다. 

뱀이 있는 위치는 2로 표시해준다.

 

Move_Snake()

이제 구체적으로 뱀의 움직임을 살펴보면, 뱀이 움직일 때,

1. 뱀 머리가 방향으로 움직인다.

2. 그 칸에 사과가 있으면 꼬리를 내비둔다.

3. 사과가 없으면 꼬리를 자른다.

 

이 동작을 수행해야하기 때문에, 머리를 늘리는 것과 꼬리를 자르는 것 두 가지의 기능을 할 수 있는 자료구조를 만들어야 한다. 그래서 큐를 조금 응용해서 뱀이 존재하는 좌표를 담은 snake 배열과 head, tail이라는 변수에 뱀의 머리와 꼬리의 index를 저장했다.

머리를 더해야할 때는 head++해서 새로운 좌표를 넣어주고, 빼야할 때는 tail++ 을 하는 방식을 이용했다. 이때 더불에 맵에도 표시를 추가하거나 제거해주면 디버깅할 때 맵의 움직임으로 뱀의 이동을 확인할 수 있다.

void addHead(int y, int x) {
	snake[head+1].y = y;
	snake[head+1].x = x;
	head++;
	map[snake[head].y][snake[head].x] = SNAKE;
}
void cutTail(void) {
	map[snake[tail].y][snake[tail].x] = 0;
	tail++;
}

위의 그림을 보면 head가 이동하는 칸이 0이다. (사과가 없다)

그럼 머리는 머리대로 움직이고 꼬리는 잘라줘야 한다. 그래서 cutTail()과 addHead()가 둘다 일어난다.

사과가 있는 경우에는 addHead()만 일어나면 된다.

int Snake_Move() {
	//머리를 다음칸에 위치시킨다.
	int ny = snake[head].y + dy[dir];
	int nx = snake[head].x + dx[dir];
	if (ny <= 0 || ny > N || nx <= 0 || nx > N) return 0; // 벽
	if (map[ny][nx] == SNAKE) return 0; //본인 몸
	if (map[ny][nx] != 1) { // 사과가 없음
		cutTail();
	}
	addHead(ny, nx);
	return 1;
}

움직이는 과정에서 머리가 본인 몸에 닿거나, 벽에 닿으면 종료한다.

 

방향 전환

방향 전환이 일어나는 시간과 회전 방향이 따로 주어진다. 이를 (시간, 방향) 구조체 배열인 cmd에 저장해두었다가 [시간]이면 [방향]으로 회전할 수 있게 했다.

L 이면 -1, R 이면 1을 저장해놔서, 그냥 단순히 dir + [방향]으로 방향을 처리해줄 수 있다.

if (cmd[t] != 0) { // 회전
  dir = dir + cmd[t];
  if (dir < 0) dir = 3;
  if (dir > 3) dir = 0;
}

 

전체 코드

#include <stdio.h>
#include <string.h>
#define MAXN 100
#define MAXK 100
#define MAXL 100
#define MAXX 10000
#define SNAKE 2

int N, K, L; // 보드크기, 사과 개수, 회전 횟수
int map[MAXN + 5][MAXN + 5];
int cmd[MAXX + 5];
int dir; // 뱀 방향

typedef struct st {
	int y, x;
}POS;
POS snake[MAXN * MAXN * 10];
int head, tail;

void addHead(int y, int x) {
	snake[head+1].y = y;
	snake[head+1].x = x;
	head++;
	map[snake[head].y][snake[head].x] = SNAKE;
}

void cutTail(void) {
	map[snake[tail].y][snake[tail].x] = 0;
	tail++;
}

int dy[] = { 0, 1, 0, -1 }; // 우하좌상
int dx[] = { 1, 0, -1, 0 };

void Get_Input(void) {
	int y, x;
	int t;
	char c;
	scanf("%d", &N);
	scanf("%d", &K); 
	// 사과 맵에 표시하기
	for (int i = 0; i < K; i++) {
		scanf("%d %d", &y, &x);
		map[y][x] = 1;
	}
	// cmd의 t시에 d로 방향 전환한다
	scanf("%d", &L);
	for (int i = 0; i < L; i++) {
		scanf("%d %c", &t, &c);
		if (c == 'L') cmd[t] = -1;
		if (c == 'D') cmd[t] = 1;
	}
}

int Snake_Move() {
	//머리를 다음칸에 위치시킨다.
	int ny = snake[head].y + dy[dir];
	int nx = snake[head].x + dx[dir];
	if (ny <= 0 || ny > N || nx <= 0 || nx > N) return 0; // 벽
	if (map[ny][nx] == SNAKE) return 0; //본인 몸
	if (map[ny][nx] != 1) { // 사과가 없음
		cutTail();
	}
	addHead(ny, nx);
	return 1;
}

void Init(void) {
	addHead(1, 1);
	tail = 1;
}

int main(void) {
	int t;
	Get_Input();
	Init();
	for (t = 0; t <= 10000; t++) {
		if (cmd[t] != 0) { // 회전
			dir = dir + cmd[t];
			if (dir < 0) dir = 3;
			if (dir > 3) dir = 0;
		}
		// 뱀이 이동한다
		if(!Snake_Move()) break;
	}
	printf("%d", t+1);
	return 0;
}