3190번: 뱀 (C언어)

문제

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

3190번: 뱀

반례 모음

https://www.acmicpc.net/board/view/56469

글 읽기 - 뱀 문제 반례모음입니다

---

#풀이

코드길이가 너무 길다.

• 구조체를 한 번도 사용해보지 않아서 연습해보고자 구조체로 구현보았다.
• 코드가 너무 길다.

 

## 입력

보드의 크기 N (2 ≤ N ≤ 100)          -> size

사과의 개수 K (0 ≤ K ≤ 100)           -> apple_count

뱀의 방향 변환 횟수 L (1 ≤ L ≤ 100) -> L

 

## 구조체, 함수, 변수 설명

• s_turn: 구조체에 time(X초)과 direct(C 방향)
• s_coord: 사과의 위치, 뱀의 위치 등에 쓰일 x, y
• s_snake: 머리의 위치(head), 길이(length), 이동방향(direction), 몸의 현재 위치(body)
  
  - s_snake.direction은 나침반을 기준으로 0은 W방향, 1은 N방향, 2는 E방향, 3은 S방향
  
  - 시작은 2(E방향)으로 시작해서 방향 변환이 왼쪽(L)일 경우, -1을 해서 1(N방향). 오른쪽(D)일 경우, +1을 해서 3(S방향).

 

• int eat_apple(t_snake snake, t_coord *apples); 
  
  - 이동한 위치에 사과가 있는지 확인해주는 함수
  
  - 사과가 있으면 1을 반환
  
  - 사과가 없으면 0을 반환

 

• void grow_up(t_snake *snake);
  
  - 사과를 먹어서 뱀의 길이(snake.length)가 길어졌을 때, 새로운 몸(new_body)을 할당해주는 함수
  
  - 새로운 크기의 배열이 생성되야하므로 기존의 포인터는 free를 해주고 => free(snake->body);
  
  - 새로운 몸을 넣어줌 => snake->body = new_body;
  
  - 뱀의 길이가 2일 경우, 처음 생성되는 것이므로 free는 하지 않는다.

 

• int head_body_crash(t_snake snake);
  
  - 뱀의 머리가 몸통에 부딪혔는지 여부를 확인하는 함수
  
  - 부딪혔으면 1을 반환
  
  - 부딪히지 않았으면 0을 반환

 

• void store_snake_body(t_snake *snake, t_coord pre_coord);
  
  - 뱀이 이동할때마다 전에 있던 위치를 snake.body에 저장해주는 함수.
  
  - 큐 방식으로 한칸씩 뒤로 밀어주고 맨 앞 인덱스에는 새로운 값(pre_coord)가 들어감

 

## 종료 조건

1. 뱀위 위치가 (1, 1)부터 시작해 x의 좌표가 0 혹은 y의 좌표가 0이 되면 종료 (소스 코드 line 103)

2. 뱀의 위치가 보드의 크기(size)를 벗어나면 종료 (소스 코드 line 103)

 

3. 뱀의 머리가 몸통의 위치에 겹치면 종료 (head_body_crash 함수)

 

## 구현 방법

0. 값을 입력. 주의: 사과의 개수(apple_count)는 0일 수 있으므로 예외처리

1. 현재 머리의 위치를 pre_coord저장

2. t_snake.direction에 저장되어 있는 진행방향으로 이동

3. 이동한 위치에 사과가 있는지 확인 => eat_apple(snake, apples)

 

4. 사과가 있으면 뱀의 길이(snake.length)를 +1시켜주고 grow_up함수를 이용해 새로운 몸통 생성.

 

5. 게임 시작 시간 1증가.

 

6. 뱀의 머리(snake.head)가 뱀의 몸통(snake.body)와 부딪혔는지 확인 (head_body_crash 함수)

 

7. 뱀의 길이(snake.length)가 2이상인 경우, 뱀의 몸통 위치를 저장 (store_snake_body 함수)

 

8. 게임 시간이 뱀이 방향을 바꿔야하는 시간과 일치할 경우, 입력해 놓은 방향으로 방향을 바꿈.
    (ex 3 D일 경우, 3초에 오른쪽으로 이동)

 

9. 반복

 

10. while문이 종료되면 시간을 출력하고, 할당했던 포인터를 free

 

예제 입력 3

 

## 예외처리 및 주의

• 동적할당을 할 경우, free를 제때하지 않으면 메모리 초과 발생
  
  
• 사과의 개수 K가 0일 수 있으므로 알아서 처리해줘야함.

 

소스 코드

#include <stdio.h>	// printf, scanf
#include <stdlib.h>	// malloc, free

typedef struct	s_turn
{
	int		time;
	char		direct;
}			t_turn;

typedef struct	s_coord
{
	int		x;
	int		y;
}			t_coord;

typedef struct	s_snake
{
	t_coord		head;
	int		length;
	int		direction;	// WNES
	t_coord		*body;
}			t_snake;

int	eat_apple(t_snake snake, t_coord *apples)
{
	int	idx;

	idx = 0;
	while ((apples + idx)->x != '\0')
	{
		if (snake.head.x == (apples + idx)->x && snake.head.y == (apples + idx)->y)
		{
			(apples + idx)->x = -1;
			(apples + idx)->y = -1;
			return (1);
		}
		idx++;
	}
	return (0);
}

void	grow_up(t_snake *snake)
{
	t_coord		*new_body;
	int		idx;

	if (!(new_body = (t_coord *)malloc(sizeof(t_coord) * (snake->length - 1))))
		return ;
	idx = 0;
	while (idx < snake->length - 2)
	{
		(new_body + idx)->x = (snake->body + idx)->x;
		(new_body + idx)->y = (snake->body + idx)->y;
		idx++;
	}
	if (snake->length >= 3)
		free(snake->body);
	snake->body = new_body;
}

int	head_body_crash(t_snake snake)
{
	int	idx;

	idx = 0;
	while (idx < snake.length - 1)
	{
		if (snake.head.x == (snake.body + idx)->x && snake.head.y ==(snake.body + idx)->y)
			return (1);
		idx++;
	}
	return (0);
}

void	store_snake_body(t_snake *snake, t_coord pre_coord)
{
	int	idx;

	idx = snake->length - 2;
	while (idx > 0)
	{
		(snake->body + idx)->x = (snake->body + idx - 1)->x;
		(snake->body + idx)->y = (snake->body + idx - 1)->y;
		idx--;
	}
	(snake->body + idx)->x = pre_coord.x;
	(snake->body + idx)->y = pre_coord.y;
}

void	get_time(int size, t_coord *apples, t_turn *turns)
{
	int		survival_time;
	t_snake 	snake;
	t_coord 	pre_coord;
	int		turn_idx;

	snake.head.x = 1;
	snake.head.y = 1;
	snake.length = 1;
	snake.direction = 2;
	survival_time = 0;
	turn_idx = 0;
	while (1 <= snake.head.x && snake.head.x <= size &&
			1 <= snake.head.y && snake.head.y <= size)
	{
		pre_coord.x = snake.head.x;
		pre_coord.y = snake.head.y;
		// snake's movement
		if (snake.direction == 1)	// 1: N
			snake.head.x -= 1;
		else if (snake.direction == 2)	// 2: E
			snake.head.y += 1;
		else if (snake.direction == 0)	// 0: W
			snake.head.y -= 1;
		else if (snake.direction == 3)	// 3: S
			snake.head.x += 1;
		// When a snake eats an apple
		if (apples && eat_apple(snake, apples))
		{
			snake.length += 1;
			grow_up(&snake);
		}
		survival_time++;
        	// When the head crashes into a body
		if (head_body_crash(snake))
			break ;
		// Store and verify the location of the snake's torso
		if (snake.length >= 2)
			store_snake_body(&snake, pre_coord);
		// A snake's turn
		if (turns && survival_time == (turns + turn_idx)->time)
		{
			if ((turns + turn_idx)->direct == 'L')
				snake.direction = (snake.direction - 1) % 4;
			else if ((turns + turn_idx)->direct == 'D')
				snake.direction = (snake.direction + 1) % 4;
			if(snake.direction == -1)
				snake.direction = 3;
			turn_idx++;
		}
	}
	printf("%d\n", survival_time);
	if (apples)
		free(snake.body);
}

int	main(void)
{
	int		size;	// Size of board
	int		apple_count;	// Number of apples
	int		L;	// Number of directional conversions
	int		idx;
	t_coord 	*apples;
	t_turn		*turns;

	scanf("%d", &size);	// size
	// apple_count, x, y
	scanf("%d", &apple_count);	
	apples = 0;
	if (apple_count)
	{
		if (!(apples = (t_coord *)malloc(sizeof(t_coord) * apple_count)))
			return (0);
		idx = -1;
		while (++idx < apple_count)
			scanf("%d %d", &(apples + idx)->x, &(apples + idx)->y);
	}
	// L, time, direct
	scanf("%d", &L);	
	if (!(turns = (t_turn *)malloc(sizeof(t_turn) * L)))
		return (0);
	idx = -1;
	while (++idx < L)
		scanf("%d %c", &(turns + idx)->time, &(turns + idx)->direct);
	get_time(size, apples, turns);
	if (apple_count)
		free(apples);
	free(turns);
	return (0);
}

 

 

---

참고

• 구조체 포인터를 선언하고 메모리 할당하기 - https://dojang.io/mod/page/view.php?id=418

C 언어 코딩 도장: 49.1 구조체 포인터를 선언하고 메모리 할당하기

• 구조체 안의 구조체 멤버에 메모리 할당하기 - https://dojang.io/mod/page/view.php?id=463

C 언어 코딩 도장: 55.2 구조체 안의 구조체 멤버에 메모리 할당하기