BOJ 3190 : 뱀 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/3190

 

 

삼성 A형은 보통 DFS/BFS 1문제, 시뮬레이션 1문제로 나온다.

 

첫번째 시뮬레이션 문제 뱀을 풀어보자.

뱀은 Snake 게임을 구현하면 된다. (구글에서 스네이크 게임 검색)

 

만들어야 함수는 다음과 같다.

1) input 함수 및 디버깅을 위한 output 함수.

2) 충돌 체크 함수.

 

MAP을 어떻게 설계하냐에 따라 푸는 방법이 조금 달라질 수 있다.

NXN 정사각 보드에서, 상하좌우 끝에 벽이 있다고 했으므로,

(0, 0) 부터 (N + 1, N + 1)을 모두 벽으로 만들고,

(1,1) ~ (N, N)을 보드로 덮어씌우자.

 

그리고 X초 뒤의 명령어 C를 저장할 때는 배열을 이용하자.

X는 최대 10000이하의 양의 정수이므로, 10000이상의 배열에 저장해서,

매 초 마다 command 배열을 command[time] 으로 확인할 수 있고,

명령어가 있으면 snake의 방향을 바꿔주면 된다.

#define MAX (100+20)
#define APPLE (5)

int N, M, L;
int MAP[MAX][MAX];
int command[10000 + 2000];

void input()
{
	int i, j;
	int r, c;
	char ch;
	scanf("%d %d", &N, &M);

	/* 모두 벽 # 으로 만든 다음, */
	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = '#';
	
    /* 움직일 수 있는 칸을 0으로 만든다. */
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)		
			MAP[r][c] = 0;

	MAP[1][1] = '>'; /* 뱀 표시 */

	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &r, &c);
		MAP[r][c] = APPLE;
	}

	scanf("%d", &L);
    
    /* 명령어 저장 */
	for (int i = 0; i < L; i++)
	{
		int X;
		char C;

		scanf("%d %c", &X, &C);
		command[X] = C;
	}
}

 

이제 snake를 움직이기 위해 다음과 같은 dr, dc 배열과 snake 구조체를 만들자.

현재 좌표 (row, column), 그리고 뱀이 움직이는 방향이 필요하다.

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0,-1,0,1 };
int dc[] = { -1,0,1,0 };

typedef struct st
{
	int r; /* 현재 좌표 row */
	int c; /* 현재 좌표 column */
	int dir; /* 현재 방향 */
}SNAKE;

int main(void)
{
	int time;

	input();

	snake.r = 1;
	snake.c = 1;
	snake.dir = 2;
    
    // ...
    
    return 0;
 }

 

최초의 좌표는 (1, 1), 최초의 방향은 오른쪽이므로 dir = 2로 init하자.

이제 while 안에서 뱀을 움직여야 한다.

 

종료 조건은 

1) 이동한 칸이 벽인 경우.

2) 자기 자신과 충돌한 경우.

 

종료 조건이 아닐 때는 다음과 같은 경우를 구현해야 한다.

1) 사과를 먹은 경우.

2) 뱀의 이동 = 머리 이동 + 몸의 이동.

3) 명령어에 대한 방향 전환.

 

머리가 가장 먼저 움직이므로, 머리를 움직인 다음, 

머리가 벽에 부딪히는지, 몸에 부딪히는지를 확인해야 한다.

(문제의 조건에서 "뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다." 라고 하였다.)

while (1)
{
	//1초 증가.
	time++;

	//이전 좌표 저장.
	int tmpR = snake.r;
	int tmpC = snake.c;

	//한칸 이동. - 머리
	snake.r += dr[snake.dir];
	snake.c += dc[snake.dir];

	//이동한 칸이 벽이면 종료.
	if (MAP[snake.r][snake.c] == '#') break;

	//이동한 칸에 자기자신이 있으면 종료.
	if (isCrash()) break;
    
    // ...
}

isCrash는 뱀의 몸과 뱀의 머리가 일치하는지 체크만 하면 된다. (최종 코드 참고)

 

종료 조건에 걸리지 않았다면, 사과를 찾은 경우를 생각해보자.

사과를 찾았다면, 다음에 뱀이 왔을 때, 사과가 있으면 안되므로, MAP을 0으로 바꿔준다. 

그리고 뱀의 길이를 1 증가 시키고, 뱀 머리의 이전 좌표를 이용하여, 뱀의 몸 좌표를 갱신한다.

if (MAP[snake.r][snake.c] == APPLE) //이동한 칸이 사과면? 뱀 길이 증가.
{
	int tmpHeadR, tmpHeadC;
	int tmpTailR, tmpTailC;
    
	MAP[snake.r][snake.c] = 0; /* 사과 제거 */

	length++; /* 늘어난 뱀 */
    
    /* 머리가 움직이기 전 좌표 */
	tmpHeadR = tmpR;
	tmpHeadC = tmpC;
	for (int k = 0; k < length;k++)
	{   /* 머리 좌표를 기준으로 몸 좌표를 1칸씩 이동 */
		tmpTailR = snakeBody[k].r;
		tmpTailC = snakeBody[k].c;

		snakeBody[k].r = tmpHeadR;
		snakeBody[k].c = tmpHeadC;

		tmpHeadR = tmpTailR;
		tmpHeadC = tmpTailC;
	}
}
else if (length > 0) //몸이 있는 경우 모두 한칸씩 이동.
{
	int tmpHeadR, tmpHeadC;
	int tmpTailR, tmpTailC;

	tmpHeadR = tmpR;
	tmpHeadC = tmpC;
	for (int k = 0; k < length;k++)
	{
		tmpTailR = snakeBody[k].r;
		tmpTailC = snakeBody[k].c;

		snakeBody[k].r = tmpHeadR;
		snakeBody[k].c = tmpHeadC;

		tmpHeadR = tmpTailR;
		tmpHeadC = tmpTailC;
	}
}

 

사과가 아닌 경우는 이동만 하면 되므로, MAP 갱신과 length 증가를 빼면 된다.

 

방향 전환은 %를 이용하여 전환하자.

if (command[time] == 'D') snake.dir = (snake.dir + 1) % 4;
else if (command[time] == 'L') snake.dir = (snake.dir + 4 - 1) % 4;

나머지 연산으로 가능한 이유는 dr, dc를 순서대로 왼쪽, 위, 오른쪽, 아래가 되도록 만들었기 때문이다.

나머지 연산이 헷갈린다면, 방향 전환에 대한 배열 table을 만들어 두면 된다.

 

예를 들면

left[0] = 1, left[1] = 2, left[2] = 3, left[3] = 0;

right[0] = 3, right[1] = 0, right[2] = 1, right[3] = 2;

 

가 되도록 만들면 위의 나머지 연산을 쓸 필요가 없다.

(사실 성능을 고려하면 나머지 연산 보다는 배열 table을 만드는게 낫다.)

 

최종 코드는 아래를 참고하자.

#include <stdio.h>

#define MAX (100+20)
#define APPLE (5)

int N, M, L;
int MAP[MAX][MAX];
int command[10000 + 2000];

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

typedef struct st
{
	int r;
	int c;
	int dir;
}SNAKE;

SNAKE snake;
SNAKE snakeBody[MAX*MAX];
int length;

void input()
{
	int i, j;
	int r, c;
	char ch;
	scanf("%d %d", &N, &M);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = '#';

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			MAP[r][c] = 0;

	MAP[1][1] = '>';

	for (int i = 0; i < M;i++)
	{
		scanf("%d %d", &r, &c);
		MAP[r][c] = APPLE;
	}

	scanf("%d", &L);
	for (int i = 0; i < L;i++)
	{
		int X;
		char C;

		scanf("%d %c", &X, &C);
		command[X] = C;
	}
}

void output()
{
	for (int r = 0; r <= N + 1; r++)
	{
		for (int c = 0;c <= N + 1; c++)
		{
			if (MAP[r][c] == '>' || MAP[r][c] == 'V') printf("%c ", MAP[r][c]);
			else if (MAP[r][c] == '#') printf("%c ", MAP[r][c]);
			else printf("%d ", MAP[r][c]);
		}
		putchar('\n');
	}
	putchar('\n');
}

int isCrash()
{
	for (int i = 0; i < length;i++)
		if (snake.r == snakeBody[i].r && snake.c == snakeBody[i].c) return 1;

	return 0;
}


int main(void)
{
	int time;

	input();

	snake.r = 1;
	snake.c = 1;
	snake.dir = 2;

	time = 0;
	while (1)
	{
		time++;

		int tmpR = snake.r;
		int tmpC = snake.c;

		snake.r += dr[snake.dir];
		snake.c += dc[snake.dir];

		if (MAP[snake.r][snake.c] == '#') break;

		if (isCrash()) break;

		if (MAP[snake.r][snake.c] == APPLE)
		{
			int tmpHeadR, tmpHeadC;
			int tmpTailR, tmpTailC;
			MAP[snake.r][snake.c] = 0;

			length++;
			tmpHeadR = tmpR;
			tmpHeadC = tmpC;
			for (int k = 0; k < length;k++)
			{
				tmpTailR = snakeBody[k].r;
				tmpTailC = snakeBody[k].c;

				snakeBody[k].r = tmpHeadR;
				snakeBody[k].c = tmpHeadC;

				tmpHeadR = tmpTailR;
				tmpHeadC = tmpTailC;
			}
		}
		else if (length > 0)
		{
			int tmpHeadR, tmpHeadC;
			int tmpTailR, tmpTailC;

			tmpHeadR = tmpR;
			tmpHeadC = tmpC;
			for (int k = 0; k < length;k++)
			{
				tmpTailR = snakeBody[k].r;
				tmpTailC = snakeBody[k].c;

				snakeBody[k].r = tmpHeadR;
				snakeBody[k].c = tmpHeadC;

				tmpHeadR = tmpTailR;
				tmpHeadC = tmpTailC;
			}
		}

		if (command[time] == 'D') snake.dir = (snake.dir + 1) % 4;
		else if (command[time] == 'L') snake.dir = (snake.dir + 4 - 1) % 4;
	}

	printf("%d\n", time);

	return 0;

}

 

마찬가지로, 실제 시험에서는 tc가 여러개이므로 초기화를 잊지말자.

뱀의 몸, 뱀의 머리, command 모두를 전체 배열에 대해 초기화 해야 한다.

int main(void)
{
	int T;
	scanf("%d", &T);

	for (int tc = 1; tc <= T; tc++)
	{
    	int time;
        
    	input(); // input에 MAP, snakeBody, command를 전체 배열에 대해 초기화 코드 추가
        
        snake.r = 1;
		snake.c = 1;
		snake.dir = 2;
        
        time = 0;
		while(1) { ... }
		
		printf("#%d %d\n", tc, time);
	}
    
    return 0;
}