BOJ 16236 : 아기 상어 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

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

 

www.acmicpc.net/problem/16236

 

이후 설명 및 입/출력은 링크 참고

 

아기 상어 구조체는 좌표와 몇 마리의 물고리를 먹었는지, 그리고 현재의 크기가 필요하다.

typedef struct st1 
{
	int r;
	int c;
	int eat;
	int size;
}SHARK;

SHARK babyshark;

 

input을 받으면서 9인 경우에 아기 상어 구조체를 초기화 해주자.

void input()
{
	scanf("%d", &N);
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			scanf("%d", &MAP[r][c]);
			
			if (MAP[r][c] == 9)
			{
				MAP[r][c] = 0; /* 자기 자신을 통과하도록 0으로 변경 */
				babyshark.r = r;
				babyshark.c = c;
				babyshark.eat = 0;
				babyshark.size = 2;
			}
		}
	}
}

 

아기 상어는 먹을 수 있는 물고기가 있는 경우, 움직여서 물고기를 먹어야 한다.

 

전체 코드 구조를 알아보자.

while (1)
{
	int ret = ALLBFS();
		
	if (ret == 0) break;
		
	time += ret;
}

 

ALLBFS는 먹을 수 있는 물고기가 있다면 그 거리를 return한다.

return값이 0이라면 종료하고, 그렇지 않다면 아기상어가 움직일 수 있는 시간에 누적한다.

 

ALLBFS는 아래처럼 작동한다.

int ALLBFS()
{
	if (checkFish() == 0) return 0; /* 잡아먹을 수 있는 물고기가 없는 경우 종료 */

	int tmpR, tmpC;

	int min = 0x7fff0000;
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
        	int length = BFS(r, c);
			if (length < min)
			{
            	/* 잡을 수 있는 물고기가 있는지 직접 거리 계산 */
            	/* 거리 계산에 따른 min 갱신, 좌표 저장 */
            }
		}
	}

	if (min == 0x7fff0000) return 0;
	
	MAP[tmpR][tmpC] = 0; /* 물고기 제거 */

	/* shark 갱신 */

	return min;
}

 

먼저 먹을 수 있는 물고기, 즉, 아기 상어보다 작은 물고기가 없다면 종료한다.

아기 상어보다 작은 물고기가 있다면, 실제로 그 물고기를 잡으러 갈 수 있는지 거리를 계산한다.

실제로 잡아먹을 수 있다면, min을 갱신하면서 좌표를 기억해둔다.

 

위의 이중 for문으로 가장 위에서 부터, 가장 왼쪽의 물고기를 탐색하므로, 아래의 조건은 해결된다.

 

이제 거리를 구하는 BFS 함수를 보자. 2차원 BFS의 거리를 재는 연습은 링크를 참고하자.

이 BFS는 잡아야 할 물고기의 좌표를 넘겨 받는다.

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

int BFS(int er, int ec)
{
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			visit[r][c] = 0;

	wp = rp = 0;

	queue[wp].r = babyshark.r;
	queue[wp++].c = babyshark.c;

	visit[babyshark.r][babyshark.c] = 1;

	while (wp > rp)
	{
		QUEUE out = queue[rp++];

		if (out.r == er && out.c == ec) return visit[out.r][out.c] - 1;

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i]; /* 주변 좌표 */
			int nc = out.c + dc[i];

			if (nr < 0 || nc < 0 || nr > N - 1 || nc > N - 1) continue;
			if (MAP[nr][nc] > babyshark.size) continue;
			
			if (visit[nr][nc] == 0) /* 벽이 아니고, 방문 하지 않은 곳 */
			{
				queue[wp].r = nr;
				queue[wp++].c = nc; /* push */

				visit[nr][nc] = visit[out.r][out.c] + 1 ; /* 방문 check + 거리 계산 */
			}
		}
	}

	return 0x7fff0000;
}

미로 탐색 문제와는 달리 visit에 거리를 저장하도록 만들었다.

MAP에는 다양한 물고기가 있기 때문에, visit에 거리를 저장하였다.

visit에 거리를 저장하면 좋은 점은, 방문 체크도 동시에 할 수 있다는 점이다.

visit이 0이면 방문하지 않은 곳, 1이상이면 방문한 것이고, 그 값이 거리이다.

하지만 실제로 처음 시작을 1로 잡았기 때문에, 실제 거리를 return할 때는 -1을 빼줘야 한다.

 

큐에 담을 수 있는 조건은, 경계를 벗어나지 않으면서, 아기 상어보다 작은 MAP인 경우만 가능하다.

그리고 BFS의 종료 조건은, 잡아야 할 물고기의 좌표를 찾으면 종료가 된다.

큐가 모두 pop되었는데도 물고기를 찾지 못하였을 경우, 최악의 min 값을 return해준다.

 

ALLBFS에서 min이 0x7fff000이라면 잡을 수 있는 물고기는 있지만, 물리적으로 잡으러 갈 수 없다는 뜻이된다.

(큰 물고기에 둘러싸인 작은 물고기는 물리적으로 잡을 수 없다.)

 

그 외 세부 조건은 아래의 코드를 참고하자.

아기 상어의 size가 커지는 조건은 eat을 증가시키고 size가 같으면 갱신하면 된다.

그리고 잡아먹을 물고기가 선택되면 좌표를 기억해두고 아기 상어의 좌표를 갱신, MAP도 0으로 갱신한다. 

#include <stdio.h>

#define MAX (20 + 10)

int N;
int MAP[MAX][MAX];
int visit[MAX][MAX];

typedef struct st1 
{
	int r;
	int c;
	int eat;
	int size;
}SHARK;

SHARK babyshark;

typedef struct st2
{
	int r;
	int c;
}QUEUE;

QUEUE queue[MAX * MAX];
int wp, rp;

void input()
{
	scanf("%d", &N);
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			scanf("%d", &MAP[r][c]);
			
			if (MAP[r][c] == 9)
			{
				MAP[r][c] = 0; /* 자기 자신을 통과하도록 0으로 변경 */
				babyshark.r = r;
				babyshark.c = c;
				babyshark.eat = 0;
				babyshark.size = 2;
			}
		}
	}
}

void output()
{
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
			printf("%d ", visit[r][c]);
		putchar('\n');
	}
}

int checkFish()
{
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N;c++)
			if (MAP[r][c] != 0 && MAP[r][c] < babyshark.size) return 1;
			
	return 0;
}

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

int BFS(int er, int ec)
{
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			visit[r][c] = 0;

	wp = rp = 0;

	queue[wp].r = babyshark.r;
	queue[wp++].c = babyshark.c;

	visit[babyshark.r][babyshark.c] = 1;

	while (wp > rp)
	{
		QUEUE out = queue[rp++];

		if (out.r == er && out.c == ec) return visit[out.r][out.c] - 1;

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i]; /* 주변 좌표 */
			int nc = out.c + dc[i];

			if (nr < 0 || nc < 0 || nr > N - 1 || nc > N - 1) continue;
			if (MAP[nr][nc] > babyshark.size) continue;
			
			if (visit[nr][nc] == 0) /* 벽이 아니고, 방문 하지 않은 곳 */
			{
				queue[wp].r = nr;
				queue[wp++].c = nc; /* push */

				visit[nr][nc] = visit[out.r][out.c] + 1 ; /* 방문 check + 거리 계산 */
			}
		}
	}

	return 0x7fff0000;
}

int ALLBFS()
{
	if (checkFish() == 0) return 0; /* 잡아먹을 수 있는 물고기가 없는 경우 종료 */

	int tmpR, tmpC;

	int min = 0x7fff0000;
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			if (MAP[r][c] == 0) continue;
			if (MAP[r][c] >= babyshark.size) continue;

			int length = BFS(r, c);
			if (length < min)
			{
				min = length;

				tmpR = r; /* 잡아 먹을 물고기의 임시 좌표 */
				tmpC = c;
			}
		}
	}

	if (min == 0x7fff0000) return 0; /* 물고기가 있지만 잡을 수 없는 경우 */
	
	MAP[tmpR][tmpC] = 0; /* 물고기 제거 */

	babyshark.r = tmpR; /* 물고기 좌표로 이동 */
	babyshark.c = tmpC;
	babyshark.eat++;

	if (babyshark.eat == babyshark.size)
	{
		babyshark.eat = 0;
		babyshark.size++;
	}

	return min;
}

int main(void)
{
	input();

	int time = 0;

	while (1)
	{
		int ret = ALLBFS();
		
		if (ret == 0) break;
		
		time += ret;
	}

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

	return 0;
}

실제 A형에서는 아기 상어를 잘 초기화 하자.