hotamul의 개발 이야기

[Algorithm][C++] BOJ 3190: 뱀 (Double Linked List) 본문

myt-algorithm-practice/Samsung SW Certi Pro

[Algorithm][C++] BOJ 3190: 뱀 (Double Linked List)

hotamul 2021. 11. 21. 23:35

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

 

3190번: 뱀

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임

www.acmicpc.net

 

풀이 핵심

1. 기존에는 stack + queue 로 풀이했다면 이번에는 double linked list를 이용해 풀이해보고자 한다. double linked list를 사용하는 이유는 꼬리를 자르는 경우 (꼬리를 잘라야 하는 경우 꼬리의 이전(post)이 꼬리가 되게 하고 꼬리를 잘라야 한다) 때문에 그렇다. 

 

2. SNAKE 구조체와 make, cut_tail 함수를 다음과 같이 만들어 준다.

struct SNAKE {
	int y, x;
	SNAKE* next;
	SNAKE* post;
};

SNAKE HEAD;
SNAKE TAIL;
SNAKE POOL[MAXN * MAXN];
int pcnt;

void move(int y, int x) {
	SNAKE* nd = &POOL[pcnt++];
	nd->y = y, nd->x = x;
	nd->post = NULL;

	if (HEAD.next == NULL) {
		HEAD.next = TAIL.next = nd;
	}
	else {
		nd->next = HEAD.next;
		HEAD.next->post = nd;
		HEAD.next = nd;
	}
	map[y][x] = 2;
}

void cut_tail() {
	SNAKE* tmp = TAIL.next->post;
	map[TAIL.next->y][TAIL.next->x] = 0;
	tmp->next = NULL;
	TAIL.next = tmp;
}

 

3. 사과가 있다면 move만 해주고 사과가 없다면 move, cut_tail 함수를 실행하도록 loop를 만든다.

 

코드

#include <cstdio>
#define MAXN	100
#define MAXL	10001

int N, K, L;
int map[MAXN][MAXN];
int dir;
const int dy[] = { 0,1,0,-1 };
const int dx[] = { 1,0,-1,0 };

struct SNAKE {
	int y, x;
	SNAKE* next;
	SNAKE* post;
};

SNAKE HEAD;
SNAKE TAIL;
SNAKE POOL[MAXN * MAXN];
int pcnt;

void move(int y, int x) {
	SNAKE* nd = &POOL[pcnt++];
	nd->y = y, nd->x = x;
	nd->post = NULL;

	if (HEAD.next == NULL) {
		HEAD.next = TAIL.next = nd;
	}
	else {
		nd->next = HEAD.next;
		HEAD.next->post = nd;
		HEAD.next = nd;
	}
	map[y][x] = 2;
}

void cut_tail() {
	SNAKE* tmp = TAIL.next->post;
	map[TAIL.next->y][TAIL.next->x] = 0;
	tmp->next = NULL;
	TAIL.next = tmp;
}

int DIR[MAXL];

int solve() {
	int time = 0;
	move(0, 0);
	dir = 0;
	while (1) {
		++time;
		int ny = HEAD.next->y + dy[dir];
		int nx = HEAD.next->x + dx[dir];
		if (ny < 0 || ny >= N || nx < 0 || nx >= N || \
			map[ny][nx] == 2) {
			break;
		}
		if (map[ny][nx] == 0) {
			move(ny, nx);
			cut_tail();
		}
		else {
			move(ny, nx);
		}
		if (DIR[time]) {
			dir = (dir + DIR[time]) % 4;
		}
	}
	return time;
}

int main() {
	int ans;
	scanf("%d %d", &N, &K);
	for (int i = 0; i < K; i++) {
		int y, x;
		scanf("%d %d", &y, &x);
		--y, --x;
		map[y][x] = 1;
	}
	scanf("%d", &L);
	for (int i = 0; i < L; i++) {
		int t; char d;
		scanf("%d %c", &t, &d);
		DIR[t] = (d == 'D' ? +1 : 3);
	}
	ans = solve();
	printf("%d", ans);
	return 0;
}
Comments