BOJ 20058 : 마법사 상어와 파이어스톰 (삼성 SW TEST A형)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

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

 

www.acmicpc.net/problem/20058

 

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

시뮬레이션 문제이므로, 그대로 구현한다.

 

먼저 input은 (1, 1)부터 받아서 주변을 MAP의 주변이 0이 되도록한다. 그러면 주변의 얼음을 체크할 때 편하다.

그리고 MAP의 size는 2^N이므로 비트 연산 (1 << N)을 이용하여 MAP_SIZE를 따로 저장한다.

int N, Q, MAP_SIZE;
int A[MAX][MAX];
int tmpA[MAX][MAX];

void input()
{
	scanf("%d %d", &N, &Q);

	MAP_SIZE = 1 << N;
	
	for (int r = 1; r <= MAP_SIZE; r++)
		for (int c = 1; c <= MAP_SIZE; c++)
			scanf("%d", &A[r][c]);
}

 

시뮬레이션은 main에서 L을 입력받으면서 실행한다.

L을 입력받으면, L에 대해 문제에 제시된 대로 칸을 나누어 MAP A를 rotate한다. 

rotate하고 나서 얼음을 녹인다.

 

이 과정을 Q번 반복하고, 남은 얼음과 가장 큰 덩어리를 구한다.

int main(void)
{
	input();

	for (int q = 0; q < Q; q++)
	{
		int L; 
		scanf("%d", &L);

		int divide = 1 << L;

		for (int r = 1; r <= MAP_SIZE; r += divide)
			for (int c = 1; c <= MAP_SIZE; c += divide)
				rotate(A, r, c, divide);

		meltIce();
	}
	
	int sum = 0;
	for (int r = 1; r <= MAP_SIZE; r++)
		for (int c = 1; c <= MAP_SIZE; c++)
			sum += A[r][c];

	printf("%d\n%d\n", sum, findBigIce());
	
	return 0;
}

---

배열을 rotate해보자.

SIZE = 4인 배열을 시계 방향으로 rotate하면 왼쪽과 같은 결과를 얻는다.

규칙을 보면 row = 4 - 1 - column, column = row가 된다.

(0, 0)의 12는 원래 배열의 (3, 0)이다. (4 - 1 - 0 = 3, 0 = 0)

 

 

A의 전체 좌표에서 특정 좌표를 기준으로 size 만큼만 회전하므로, 기준 좌표 sr, sc를 넘겨서 회전한다.

void rotate(int map[MAX][MAX], int sr, int sc, int size)
{
	for (int r = 0; r < size; r++)
		for (int c = 0; c < size; c++)
			tmpA[r][c] = map[sr + size - 1 - c][sc + r];

	for (int r = 0; r < size; r++)
		for (int c = 0; c < size; c++)
			map[sr + r][sc + c] = tmpA[r][c];
}

 

얼음을 녹이는 것은 간단하다.

MAP 주변 4방향을 탐색하기 위해 dr, dc 배열을 선언하고, A[r][c]의 4방향 중 값이 0인 좌표를 센다.

얼음은 동시에 녹기 때문에, 녹여야하는 배열을 ICE 배열에 저장하고, 마지막에 한꺼번에 녹인다.

이미 얼음이 없는 곳은 탐색할 필요가 없다(continue).

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

void meltIce()
{
	int ICE[MAX][MAX] = { 0 };

	for (int r = 1; r <= MAP_SIZE; r++)
	{
		for (int c = 1; c <= MAP_SIZE; c++)
		{
			if (A[r][c] == 0) continue;

			int cnt = 0;
			for (int i = 0; i < 4; i++)
			{
				int nr, nc;

				nr = r + dr[i];
				nc = c + dc[i];

				cnt += !A[nr][nc];
			}

			if (cnt >= 2) ICE[r][c] = 1;
		}
	}

	for (int r = 1; r <= MAP_SIZE; r++)
		for (int c = 1; c <= MAP_SIZE; c++)
			A[r][c] -= ICE[r][c];
}	

 

얼음의 합은 시뮬레이션 종료 후, A의 값을 모두 더하면 된다.

int sum = 0;
for (int r = 1; r <= MAP_SIZE; r++)
	for (int c = 1; c <= MAP_SIZE; c++)
		sum += A[r][c];

 

마지막으로 가장 큰 덩어리를 찾아야한다.

단지번호붙이기에서 사용한 2차원 BFS 탐색으로 가장 큰 구역을 찾을 수 있다.

int BFS(int r, int c, int visit[MAX][MAX])
{
	int cnt;

	wp = rp = 0;

	cnt = 1;

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

	visit[r][c] = 1;

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

		for (int i = 0; i < 4;i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (visit[nr][nc] == 0 && A[nr][nc] != 0)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				visit[nr][nc] = 1;
				cnt++;
			}
		}
	}

	return cnt;
}

int findBigIce()
{
	int visit[MAX][MAX] = { 0 };

	int max = 0;

	for (int r = 1; r <= MAP_SIZE; r++)
	{
		for (int c = 1; c <= MAP_SIZE; c++)
		{
			if (A[r][c] == 0 || visit[r][c] == 1) continue;

			int tmp = BFS(r, c, visit);
			if (max < tmp) max = tmp;
		}
	}

	return max;
}

방문한 곳과 얼음이 없는 곳에서는 BFS를 실행하지 않는다.

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (64 + 5)

int N, Q, MAP_SIZE;
int A[MAX][MAX];
int tmpA[MAX][MAX];

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

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

void input()
{
	scanf("%d %d", &N, &Q);

	MAP_SIZE = 1 << N;

	for (int r = 1; r <= MAP_SIZE; r++)
		for (int c = 1; c <= MAP_SIZE; c++)
			scanf("%d", &A[r][c]);
}

void output(int map[MAX][MAX])
{
	for (int r = 1; r <= MAP_SIZE; r++)
	{
		for (int c = 1; c <= MAP_SIZE; c++)
			printf("%d ", map[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

void rotate(int map[MAX][MAX], int sr, int sc, int size)
{
	for (int r = 0; r < size; r++)
		for (int c = 0; c < size; c++)
			tmpA[r][c] = map[sr + size - 1 - c][sc + r];

	for (int r = 0; r < size; r++)
		for (int c = 0; c < size; c++)
			map[sr + r][sc + c] = tmpA[r][c];
}

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

void meltIce()
{
	int ICE[MAX][MAX] = { 0 };

	for (int r = 1; r <= MAP_SIZE; r++)
	{
		for (int c = 1; c <= MAP_SIZE; c++)
		{
			if (A[r][c] == 0) continue;

			int cnt = 0;
			for (int i = 0; i < 4; i++)
			{
				int nr, nc;

				nr = r + dr[i];
				nc = c + dc[i];

				cnt += !A[nr][nc];
			}

			if (cnt >= 2) ICE[r][c] = 1;
		}
	}

	for (int r = 1; r <= MAP_SIZE; r++)
		for (int c = 1; c <= MAP_SIZE; c++)
			A[r][c] -= ICE[r][c];
}

int BFS(int r, int c, int visit[MAX][MAX])
{
	int cnt;

	wp = rp = 0;

	cnt = 1;

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

	visit[r][c] = 1;

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

		for (int i = 0; i < 4;i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (visit[nr][nc] == 0 && A[nr][nc] != 0)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				visit[nr][nc] = 1;
				cnt++;
			}
		}
	}

	return cnt;
}

int findBigIce()
{
	int visit[MAX][MAX] = { 0 };

	int max = 0;

	for (int r = 1; r <= MAP_SIZE; r++)
	{
		for (int c = 1; c <= MAP_SIZE; c++)
		{
			if (A[r][c] == 0 || visit[r][c] == 1) continue;

			int tmp = BFS(r, c, visit);
			if (max < tmp) max = tmp;
		}
	}

	return max;
}

int main(void)
{
	input();

	for (int q = 0; q < Q; q++)
	{
		int L;
		scanf("%d", &L);

		int divide = 1 << L;

		for (int r = 1; r <= MAP_SIZE; r += divide)
			for (int c = 1; c <= MAP_SIZE; c += divide)
				rotate(A, r, c, divide);

		meltIce();
	}

	int sum = 0;
	for (int r = 1; r <= MAP_SIZE; r++)
		for (int c = 1; c <= MAP_SIZE; c++)
			sum += A[r][c];

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

	return 0;
}