BOJ 20056 : 마법사 상어와 파이어볼 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

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

 

www.acmicpc.net/problem/20056

 

시뮬레이션 문제는 시키는 대로 풀면 된다.

 

먼저 FIREBALL은 자신의 좌표(r,c), 질량(m), 속도(s), 방향(d)를 가진다.

FIREBALL이 얼마나 많아질지 예측할 수 없으므로 적당히 크게 메모리를 잡는다.

M은 최대 2500, 1000회 시뮬레이션이 진행되지만 의외로 작은 메모리도 pass한다.

(실제 A형을 응시한다면 최대한 메모리를 넉넉하게 잡으면 된다.)

typedef struct st1
{
	int r;
	int c;
	int m;
	int s;
	int d;
}FIREBALL;

FIREBALL fireball[10000 + 5000];
int fcnt;

 

이동한 파이어볼을 저장할 MAP은 구조체로 선언한다.

이 문제에서 MAP은 전역으로 선언하지 않고, 매 시뮬레이션마다 reset해서 사용한다.

파이어볼이 MAP[r][c]에 오면 질량 m, 속도 s는 누적한다.

방향은 가장 나중에 들어온 방향만 기억한다. 파이어볼이 1개만 있는 경우 처리를 위해 필요하다.

해당 방향이 홀수인지 짝수인지 체크하여 odd나 even을 증가시킨다.

그리고 count에 총 파이어볼을 센다.

typedef struct st2
{
	int m;
	int s;
	int d;
	int odd;
	int even;
	int count;
}INFO;

 

input에서는 fireball에 최초의 파이어볼을 저장하고, fcnt를 증가시킨다.

void input()
{
	scanf("%d %d %d", &N, &M, &K);
	
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d %d %d %d", &fireball[fcnt].r, &fireball[fcnt].c, &fireball[fcnt].m, &fireball[fcnt].s, &fireball[fcnt].d);
		fcnt++;
	}
}

---

이제 simulation 해보자.

8방향으로 이동하기 위한 배열은 문제에 주어진대로 선언한다.

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

 

simulate는 크게 2개로 구분된다.

 

1) fireball을 이동시켜 MAP에 정보를 저장시킨다.

2) MAP을 보고 다시 fireball을 생성한다.

void simulate()
{
	for (int i = 0; i < K; i++) /* K번 시뮬레이션 */
	{
		/* fireball의 이동 */
        
		INFO MAP[MAX][MAX] = { 0 };
        
		...
        
		/* MAP을 보고 fireball을 다시 생성 */
		...
	}
}

 

fireball은 빈 MAP에 fireball 배열을 이동시키면 된다.

격자의 1번과 N번 행/열이 연결되어 있으므로 이동거리를 계산할 때 아래의 처리가 필요하다.

 

1) 속력 s가 최대 1000으로 N보다 커질 수 있기 때문에 나머지 연산을 한 후에 방향에 곱해준다.

2) 변경된 nr, nc도 1과 N사이의 범위를 초과한다면 조정한다. 

 

그리고 질량, 속도는 누적, 방향은 마지막에 들어온 파이어볼의 방향을 저장한다.

그리고 방향을 체크해서 odd, even을 증가하고, count도 증가시킨다.

/* fireball의 이동 */

INFO MAP[MAX][MAX] = { 0 };

for (int f = 0; f < fcnt; f++)
{
	int nr, nc;

	nr = fireball[f].r + dr[fireball[f].d] * (fireball[f].s % N); /* speed가 N보다 클 수 있다. */
	nc = fireball[f].c + dc[fireball[f].d] * (fireball[f].s % N);

	if (nr > N) nr -= N; /* 범위 조정 */
	if (nc > N) nc -= N;
	if (nr < 1) nr += N;
	if (nc < 1) nc += N;

	MAP[nr][nc].m += fireball[f].m;
	MAP[nr][nc].s += fireball[f].s;
	MAP[nr][nc].d = fireball[f].d; /* fireball이 1개인 경우만 유효 */

	if (fireball[f].d & 1) MAP[nr][nc].odd++;
	else MAP[nr][nc].even++;

	MAP[nr][nc].count++;
}

 

이렇게 MAP에 정보를 누적하면 3가지 경우로 나뉜다.

 

1) MAP[r][c].count = 0인 경우 → 무시하고 continue;

2) MAP[r][c].count = 1인 경우 → MAP[r][c]의 정보를 그대로 fireball에 다시 추가한다.

3) MAP[r][c].count >= 2인 경우 → 문제에 제공한대로 fireball에 다시 추가한다.

 

먼저 모든 fireball의 정보를 MAP에 저장했으므로 fcnt = 0으로 초기화한다.

 

0인 경우는 continue, 1인 경우는 정보를 그대로 담고 fcnt를 증가시킨다.

2이상인 경우에 m을 5로 나눠서 0이 아닌 경우만 정보를 추가한다.

 

odd나 even의 count가 동일하다면 문제의 조건에 의해 0, 2, 4, 6의 방향으로 fireball을 4개 추가하고,

그렇지 않다면 1, 3, 5, 7의 방향으로 fireball을 4개 추가한다.

 

그 외 처리는 문제가 시키는대로 처리하였다.

/* MAP을 보고 fireball을 다시 생성 */

fcnt = 0;
		
for (int r = 1; r <= N; r++)
{
	for (int c = 1; c <= N; c++)
	{
		if (MAP[r][c].count == 0) continue;
				
		if (MAP[r][c].count == 1)
		{
			fireball[fcnt].r = r;
			fireball[fcnt].c = c;
			fireball[fcnt].m = MAP[r][c].m;
			fireball[fcnt].s = MAP[r][c].s;
			fireball[fcnt].d = MAP[r][c].d;
			fcnt++;

			continue;
		}
				
		if (MAP[r][c].m / 5 == 0) continue;

		int dir[4] = { 0 };
		if (MAP[r][c].odd == MAP[r][c].count || MAP[r][c].even == MAP[r][c].count)
			dir[0] = 0, dir[1] = 2, dir[2] = 4, dir[3] = 6;
		else
			dir[0] = 1, dir[1] = 3, dir[2] = 5, dir[3] = 7;
				
		for (int f = 0; f < 4; f++)
		{
			fireball[fcnt].r = r;
			fireball[fcnt].c = c;
			fireball[fcnt].m = MAP[r][c].m / 5;
			fireball[fcnt].s = MAP[r][c].s / MAP[r][c].count;
			fireball[fcnt].d = dir[f];
			fcnt++;
		}
	}
}

 

마지막으로 fireball과 fcnt를 보고 남은 파이어볼의 질량을 합치면 된다.

이 코드는 최종 코드를 참고하자.

#include <stdio.h>

#define MAX (50 + 5)

int N, M, K;

typedef struct st1
{
	int r;
	int c;
	int m;
	int s;
	int d;
}FIREBALL;

FIREBALL fireball[10000 + 5000];
int fcnt;

typedef struct st2
{
	int m;
	int s;
	int d;
	int odd;
	int even;
	int count;
}INFO;

void input()
{
	scanf("%d %d %d", &N, &M, &K);
	
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d %d %d %d", &fireball[fcnt].r, &fireball[fcnt].c, &fireball[fcnt].m, &fireball[fcnt].s, &fireball[fcnt].d);
		fcnt++;
	}
}

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

void simulate()
{
	for (int i = 0; i < K; i++)
	{
		/* fireball의 이동 */

		INFO MAP[MAX][MAX] = { 0 };

		for (int f = 0; f < fcnt; f++)
		{
			int nr, nc;

			nr = fireball[f].r + dr[fireball[f].d] * (fireball[f].s % N); /* speed가 N보다 클 수 있다. */
			nc = fireball[f].c + dc[fireball[f].d] * (fireball[f].s % N);

			if (nr > N) nr -= N;
			if (nc > N) nc -= N;
			if (nr < 1) nr += N;
			if (nc < 1) nc += N;

			MAP[nr][nc].m += fireball[f].m;
			MAP[nr][nc].s += fireball[f].s;
			MAP[nr][nc].d = fireball[f].d; /* fireball이 1개인 경우만 유효 */

			if (fireball[f].d & 1) MAP[nr][nc].odd++;
			else MAP[nr][nc].even++;

			MAP[nr][nc].count++;
		}

		/* MAP을 보고 fireball을 다시 생성 */

		fcnt = 0;
		
		for (int r = 1; r <= N; r++)
		{
			for (int c = 1; c <= N; c++)
			{
				if (MAP[r][c].count == 0) continue;
				
				if (MAP[r][c].count == 1)
				{
					fireball[fcnt].r = r;
					fireball[fcnt].c = c;
					fireball[fcnt].m = MAP[r][c].m;
					fireball[fcnt].s = MAP[r][c].s;
					fireball[fcnt].d = MAP[r][c].d;
					fcnt++;

					continue;
				}
				
				if (MAP[r][c].m / 5 == 0) continue;

				int dir[4] = { 0 };
				if (MAP[r][c].odd == MAP[r][c].count || MAP[r][c].even == MAP[r][c].count)
					dir[0] = 0, dir[1] = 2, dir[2] = 4, dir[3] = 6;
				else
					dir[0] = 1, dir[1] = 3, dir[2] = 5, dir[3] = 7;
				
				for (int f = 0; f < 4; f++)
				{
					fireball[fcnt].r = r;
					fireball[fcnt].c = c;
					fireball[fcnt].m = MAP[r][c].m / 5;
					fireball[fcnt].s = MAP[r][c].s / MAP[r][c].count;
					fireball[fcnt].d = dir[f];
					fcnt++;
				}
			}
		}
	}
}

int main(void)
{
	input();

	simulate();

	int sum = 0;
	for (int f = 0; f < fcnt; f++) sum += fireball[f].m;

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

	return 0;
}

 

실제 A형 tc가 여러 개이므로, 매 tc마다 fcnt = 0으로 초기화를 해야 한다.