BOJ 19237 : 어른 상어 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

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

 

www.acmicpc.net/problem/19237

 

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

 

시뮬레이션 문제는 그대로 구현만 하면 된다.

 

먼저, MAP에는 number, current, time이 필요하다.

number는 자신의 냄새를 찾기 위해 사용하고, current는 실제 현재 MAP에 있는 상어의 번호이다.

그리고 time은 냄새의 유효시간이다.

 

SHARK에는 상어의 좌표 (r, c), 방향, 방향에 대한 우선순위 2차원 배열, 생존 여부가 필요하다.

typedef struct st1
{
	int number;
	int current;
	int time;
}INFO;

INFO MAP[MAX][MAX];

typedef struct st2
{
	int r;
	int c;
	int dir;
	int priority[5][5]; /* 방향에 대한 우선순위 */
	int dead; /* 생존 여부 */
}SHARK;

SHARK shark[MAX * MAX];

 

상어의 이동을 편리하게 하기 위해, MAP 주변은 number을 -1로 표시하여 벽을 세우자.

그 외 input 값으로 MAP과 shark에 정보를 채운다.

void input()
{
	scanf("%d %d %d", &N, &M, &K);
	
	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c].number = -1;

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

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			int in;

			scanf("%d", &in);

			if (in)
			{
				shark[in].r = r;
				shark[in].c = c;
			}
		}
	}

	for (int i = 1; i <= M; i++)
	{
		int dir;
		scanf("%d", &dir);
		shark[i].dir = dir;
	}

	for (int i = 1; i <= M; i++)
		for (int d = 1; d <= 4; d++)
			scanf("%d %d %d %d", &shark[i].priority[d][1], &shark[i].priority[d][2], &shark[i].priority[d][3], &shark[i].priority[d][4]);
}

---

문제의 핵심은 상어가 다음으로 갈 방향을 정하는 함수를 만드는 것이다.

findDirection은 상어의 정보와 상어의 번호를 받아서 다음 방향을 찾는다.

먼저 현재 방향에 대한 다음 방향의 우선순위 priority를 보고 벽인 경우는 다음 우선순위로 넘긴다.

다음 방향이 아무 냄새가 없는 경우라면, 그 방향을 return 한다.

 

이렇게 해도 방향이 정해지지 않는다면, 자신의 냄새를 찾는다.

이때, 자신의 냄새도 방향에 대한 우선순위를 기준으로 찾아야 한다.

상어가 처음부터 이동을 못 하는 경우는 없다고 했으므로, 이 경우는 반드시 존재한다.

혹시나 못 찾는 경우를 대비해 printf log와 return -1을 해두면, debugging이 쉬워진다.

(continue나 return 조건을 착각해서 나타나는 현상으로 볼 수 있다.)

/* 1: 위, 2: 아래, 3: 왼쪽, 4: 오른쪽 */
int dr[] = { 0, -1, 1, 0, 0 };
int dc[] = { 0, 0, 0, -1, 1 };

int findDirection(SHARK shark, int number)
{	
	int currentDir = shark.dir;
	
	for (int d = 1; d <= 4; d++)
	{
		int nr, nc, nextDir;
		
		nextDir = shark.priority[currentDir][d]; /* 우선순위에 대한 다음 좌표 */
		nr = shark.r + dr[nextDir];
		nc = shark.c + dc[nextDir];

		if (MAP[nr][nc].number == -1) continue; /* 벽인 경우 */
		if (MAP[nr][nc].time == 0) return nextDir; /* 아무 냄새가 없는 경우 */
	}
	
    /* 벽이거나 주변에 모두 냄새가 있는 경우 */
	for (int d = 1; d <= 4; d++)
	{
		/* 자신의 체취 찾기 */

		int nr, nc, nextDir;
		
		nextDir = shark.priority[currentDir][d];
		nr = shark.r + dr[nextDir];
		nc = shark.c + dc[nextDir];

		if (MAP[nr][nc].number == number) return nextDir;
	}

	printf("impossible case!\n");
	return -1; /* error */
}

---

simulate 함수는 1000번동안 상어를 움직이고, 1번 상어만 남지 않으면 -1을 return하도록 만든다.

simulate는 아래와 같이 만든다.

 

1) 냄새 뿌리기

2) 이동 및 상어 dead 처리

3) 한 마리만 남았는지 체크

4) 냄새 time 감소

 

3)의 한 마리만 남은 경우는 상어의 수 M에서 죽는 경우마다 감소시키면 된다.

1번 상어가 가장 작은 번호이기 때문에 한 마리만 남는 경우는 반드시 1번 상어가 남는 경우가 된다.

 

1) 냄새 뿌리기

죽은 상어는 무시하고, 상어의 좌표를 이용해 MAP에 number와 time을 표시한다.

/* 냄새 뿌리기 */
for (int s = 1; s <= M; s++)
{
	if (shark[s].dead) continue;

	MAP[shark[s].r][shark[s].c].number = s;
	MAP[shark[s].r][shark[s].c].time = K;
}

 

2) 이동 및 상어 dead 처리

죽은 상어는 무시한다.

위에서 만든 findDirection으로 다음 방향을 찾는다.

상어는 동시에 움직이지만, 실제 코드는 한 마리씩 움직여야 하므로, 이미 상어가 있는지 체크해야한다.

 

이미 상어가 있는 경우, 전체 상어 수인 sharkCount를 감소한다.

그리고 상어의 번호(aleady)와 현재 상어(s)를 비교해서, 작은 번호를 죽인다. (dead = 1)

이때, 현재 상어가 큰 번호면 이동 처리까지 해줘야 한다.

/* 이동 및 상어 dead 처리 */
for (int s = 1; s <= M; s++)
{
	if (shark[s].dead) continue;
			
	int nr, nc, dir;

	dir = findDirection(shark[s], s);

	nr = shark[s].r + dr[dir];
	nc = shark[s].c + dc[dir];

	if (MAP[nr][nc].current) /* 이미 상어가 있는 경우 */
	{
		int alreadySharkNumber = MAP[nr][nc].current;

		sharkCount--;

		if (alreadySharkNumber < s) shark[s].dead = 1;
		else
		{
			shark[alreadySharkNumber].dead = 1;

			shark[s].r = nr;
			shark[s].c = nc;
			shark[s].dir = dir;

			MAP[nr][nc].current = s;
			MAP[nr][nc].number = s;
		}
	}
	else
	{
		shark[s].r = nr;
		shark[s].c = nc;
		shark[s].dir = dir;
				
		MAP[nr][nc].current = s;
		MAP[nr][nc].number = s;
	}
}

for (int s = 1; s <= M; s++) MAP[shark[s].r][shark[s].c].current = 0;

마지막으로 current는 0으로 초기화한다. 동시에 이동하기 위해 임시로 필요한 변수이기 때문이다.

current를 0으로 해두지 않으면, 다음 차례에서 상어가 움직일 때, 상어가 있는 것으로 간주하여 방향이 변경된다.

 

3) 한 마리만 남았는지 체크

4) 냄새 time 감소

sharkCount를 보고 return을 하면된다.

한 마리만 남지 않았다면, MAP의 time이 있는 경우만 -1씩 뺀다.

/* 한 마리만 남은 경우 종료 */
if (sharkCount == 1) return t;

/* time 감소 */
for (int r = 1; r <= N; r++)
	for (int c = 1; c <= N; c++)
		if (MAP[r][c].time) MAP[r][c].time--;

 

전체 코드는 아래를 참고하자.

#include <stdio.h>

#define MAX (20 + 5)

int N, M, K;

typedef struct st1
{
	int number;
	int current;
	int time;
}INFO;

INFO MAP[MAX][MAX];

typedef struct st2
{
	int r;
	int c;
	int dir;
	int priority[5][5];
	int dead;
}SHARK;

SHARK shark[MAX * MAX];

void input()
{
	scanf("%d %d %d", &N, &M, &K);
	
	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c].number = -1;

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

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			int in;

			scanf("%d", &in);

			if (in)
			{
				shark[in].r = r;
				shark[in].c = c;
			}
		}
	}

	for (int i = 1; i <= M; i++)
	{
		int dir;
		scanf("%d", &dir);
		shark[i].dir = dir;
	}

	for (int i = 1; i <= M; i++)
		for (int d = 1; d <= 4; d++)
			scanf("%d %d %d %d", &shark[i].priority[d][1], &shark[i].priority[d][2], &shark[i].priority[d][3], &shark[i].priority[d][4]);
}

void output()
{
	for (int i = 1; i <= M; i++)
		printf("shark[%d] : r %d, c %d, dir %d, dead %d\n", i, shark[i].r, shark[i].c, shark[i].dir, shark[i].dead);
	putchar('\n');

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			int current = 0;
			for (int s = 1; s <= M; s++)
				if (r == shark[s].r && c == shark[s].c) current = s;

			printf("(%d, %d, %d) ", MAP[r][c].number, MAP[r][c].time, current);
		}
		putchar('\n');
	}
	putchar('\n');
}

/* 1: 위, 2: 아래, 3: 왼쪽, 4: 오른쪽 */
int dr[] = { 0, -1, 1, 0, 0 };
int dc[] = { 0, 0, 0, -1, 1 };

int findDirection(SHARK shark, int number)
{	
	int currentDir = shark.dir;
	
	for (int d = 1; d <= 4; d++)
	{
		int nr, nc, nextDir;
		
		nextDir = shark.priority[currentDir][d]; /* 우선순위에 대한 다음 좌표 */
		nr = shark.r + dr[nextDir];
		nc = shark.c + dc[nextDir];

		if (MAP[nr][nc].number == -1) continue; /* 벽인 경우 */
		if (MAP[nr][nc].time == 0) return nextDir; /* 아무 냄새가 없는 경우 */
	}

	/* 벽이거나 주변에 모두 냄새가 있는 경우 */
	for (int d = 1; d <= 4; d++)
	{
		/* 자신의 체취 찾기 */

		int nr, nc, nextDir;
		
		nextDir = shark.priority[currentDir][d];
		nr = shark.r + dr[nextDir];
		nc = shark.c + dc[nextDir];

		if (MAP[nr][nc].number == number) return nextDir;
	}

	printf("impossible case!\n");
	return -1; /* error */
}

int simulate()
{
	int sharkCount = M;
	for (int t = 1; t <= 1000; t++)
	{
		/* 냄새 뿌리기 */
		for (int s = 1; s <= M; s++)
		{
			if (shark[s].dead) continue;

			MAP[shark[s].r][shark[s].c].number = s;
			MAP[shark[s].r][shark[s].c].time = K;
		}

		/* 이동 및 상어 dead 처리 */
		for (int s = 1; s <= M; s++)
		{
			if (shark[s].dead) continue;
			
			int nr, nc, dir;

			dir = findDirection(shark[s], s);

			nr = shark[s].r + dr[dir];
			nc = shark[s].c + dc[dir];

			if (MAP[nr][nc].current) /* 이미 상어가 있는 경우 */
			{
				int alreadySharkNumber = MAP[nr][nc].current;

				sharkCount--;

				if (alreadySharkNumber < s) shark[s].dead = 1;
				else
				{
					shark[alreadySharkNumber].dead = 1;

					shark[s].r = nr;
					shark[s].c = nc;
					shark[s].dir = dir;

					MAP[nr][nc].current = s;
					MAP[nr][nc].number = s;
				}
			}
			else
			{
				shark[s].r = nr;
				shark[s].c = nc;
				shark[s].dir = dir;
				
				MAP[nr][nc].current = s;
				MAP[nr][nc].number = s;
			}
		}

		for (int s = 1; s <= M; s++) MAP[shark[s].r][shark[s].c].current = 0;

		/* 한 마리만 남은 경우 종료 */
		if (sharkCount == 1) return t;

		/* time 감소 */
		for (int r = 1; r <= N; r++)
			for (int c = 1; c <= N; c++)
				if (MAP[r][c].time) MAP[r][c].time--;
	}

	return -1;
}

int main(void)
{
	input();

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

	return 0;
}

 

실제 A형의 tc는 여러 개이므로, MAP과 shark의 dead를 초기화해야 한다.