21611번: 마법사 상어와 블리자드

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (

www.acmicpc.net

문제

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바리기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (r, c)는 격자의 r행 c열을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이며 마법사 상어는 ((N+1)/2, (N+1)/2)에 있다.

일부 칸과 칸 사이에는 벽이 세워져 있으며, 다음은 N = 3, 5, 7인 경우의 예시이다. 실선은 벽이고, 점선은 벽이 아니다. 칸에 적혀있는 수는 칸의 번호이다.

가장 처음에 상어가 있는 칸을 제외한 나머지 칸에는 구슬이 하나 들어갈 수 있다. 구슬은 1번 구슬, 2번 구슬, 3번 구슬이 있다. 같은 번호를 가진 구슬이 번호가 연속하는 칸에 있으면, 그 구슬을 연속하는 구슬이라고 한다. 다음은 N = 7인 경우 예시이다. 

블리자드 마법을 시전하려면 방향 di와 거리 si를 정해야 한다. 총 4가지 방향 ↑, ↓, ←, →가 있고, 정수 1, 2, 3, 4로 나타낸다. 상어는 di 방향으로 거리가 si 이하인 모든 칸에 얼음 파편을 던져 그 칸에 있는 구슬을 모두 파괴한다. 구슬이 파괴되면 그 칸은 구슬이 들어있지 않은 빈 칸이 된다. 얼음 파편은 벽의 위로 떨어지기 때문에, 벽은 파괴되지 않는다.

다음 예시는 방향은 아래, 거리는 2인 경우이다.

만약 어떤 칸 A의 번호보다 번호가 하나 작은 칸이 빈 칸이면, A에 있는 구슬은 그 빈 칸으로 이동한다. 이 이동은 더 이상 구슬이 이동하지 않을 때까지 반복된다. 따라서, 구슬이 파괴된 후에는 빈 칸이 생겨 구슬이 이동하고, 구슬이 모두 이동한 결과는 다음과 같다.

이제 구슬이 폭발하는 단계이다. 폭발하는 구슬은 4개 이상 연속하는 구슬이 있을 때 발생한다. 다음은 왼쪽 그림은 위의 상태에서 폭발하는 구슬이 들어있는 칸을 파란색과 초록색으로 표시한 것이고, 오른쪽 그림은 구슬이 폭발한 후의 상태이다.

구슬이 폭발해 빈 칸이 생겼으니 다시 구슬이 이동한다. 구슬이 이동한 후에는 다시 구슬이 폭발하는 단계이고, 이 과정은 더 이상 폭발하는 구슬이 없을때까지 반복된다. 구슬이 폭발한 후의 상태에서 구슬이 이동하면 다음과 같다.

위의 상태는 4개 이상 연속하는 구슬이 있기 때문에 구슬이 다시 폭발하게 된다.

이제 더 이상 폭발한 구슬이 없기 때문에, 구슬이 변화하는 단계가 된다. 연속하는 구슬은 하나의 그룹이라고 한다. 다음은 1번 구슬은 빨간색, 2번 구슬은 파란색, 3번 구슬은 보라색으로 표시한 그림이다.

하나의 그룹은 두 개의 구슬 A와 B로 변한다. 구슬 A의 번호는 그룹에 들어있는 구슬의 개수이고, B는 그룹을 이루고 있는 구슬의 번호이다. 구슬은 다시 그룹의 순서대로 1번 칸부터 차례대로 A, B의 순서로 칸에 들어간다. 다음 그림은 구슬이 변화한 후이고, 색은 구분하기 위해 위의 그림에 있는 그룹의 색을 그대로 사용했다. 만약, 구슬이 칸의 수보다 많아 칸에 들어가지 못하는 경우 그러한 구슬은 사라진다.

 

마법사 상어는 블리자드를 총 M번 시전했다. 시전한 마법의 정보가 주어졌을 때, 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)를 구해보자.

입력

첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 격자에 들어있는 구슬의 정보가 주어진다. r번째 행의 c번째 정수는 (r, c)에 들어있는 구슬의 번호를 의미한다. 어떤 칸에 구슬이 없으면 0이 주어진다. 상어가 있는 칸도 항상 0이 주어진다.

다음 M개의 줄에는 블리자드 마법의 방향 di와 거리 si가 한 줄에 하나씩 마법을 시전한 순서대로 주어진다.

출력

첫째 줄에 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)를 출력한다.

제한

  • 3 ≤ N ≤ 49
  • N은 홀수
  • 1 ≤ M ≤ 100
  • 1 ≤ di ≤ 4
  • 1 ≤ si ≤ (N-1)/2
  • 칸에 들어있는 구슬이 K개라면, 구슬이 들어있는 칸의 번호는 1번부터 K번까지이다.
  • 입력으로 주어진 격자에는 4개 이상 연속하는 구슬이 없다.

예제 입력 1

7 1
0 0 0 0 0 0 0
3 2 1 3 2 3 0
2 1 2 1 2 1 0
2 1 1 0 2 1 1
3 3 2 3 2 1 2
3 3 3 1 3 3 2
2 3 2 2 3 2 3
2 2

예제 출력 1

28

예제 입력 2

7 4
0 0 0 2 3 2 3
1 2 3 1 2 3 1
2 3 1 2 3 1 2
1 2 3 0 2 3 1
2 3 1 2 3 1 2
3 1 2 3 1 2 3
1 2 3 1 2 3 1
1 3
2 2
3 1
4 3

예제 출력 2

0
 

예제 입력 3

7 4
1 1 1 2 2 2 3
1 2 2 1 2 2 3
1 3 3 2 3 1 2
1 2 2 0 3 2 2
3 1 2 2 3 2 2
3 1 2 1 1 2 1
3 1 2 2 2 1 1
1 3
2 2
3 1
4 3

예제 출력 3

39
 

예제 입력 4

7 7
1 1 1 2 2 2 3
1 2 2 1 2 2 3
1 3 3 2 3 1 2
1 2 2 0 3 2 2
3 1 2 2 3 2 2
3 1 2 1 1 2 1
3 1 2 2 2 1 1
1 3
2 2
3 1
4 3
1 3
1 1
1 3

예제 출력 4

62

알고리즘 분류

  • 구현
  • 시뮬레이션
  • 자료 구조

풀이

역시나 삼성 기출문제답게 약간 까다로운 구현 문제였다.

본인은 2차원 배열과 1차원 배열을 같이 사용했는데, 2차원 배열이 필요 없다는 글도 보았다. 1차원 배열을 사용하면서 스택을 사용하는 것도 괜찮아 보인다. 물론 시도는 하지 않았다.

1. 우선 2차원 배열마다 번호를 매긴다. 여기서 번호를 매기는 알고리즘은 20057번: 마법사 상어와 토네이도에서 사용했던 것에서 착안하였다.

2. 그리고 N*N개의 수를 받으면서, 1부터 N*N-1까지의 칸에 있는 구슬의 번호를 나타내는 Bead_Number라는 배열을 사용하였다.

3. 블리자드 마법을 시전할 때, D방향으로 S개의 칸에 있는 구슬을 파괴한다.

4. 이제 구슬이 움직이는데, 아까 선언한 1차원 배열 Bead_Number를 통하여 현재 칸보다 번호가 작은 칸 중 빈 칸이 있으면 구슬이 이동하도록 하였다.

5. 이제 폭발이 일어나는데, 구슬들을 탐색하면서 연속해서 4개 이상의 구슬이 나열되어 있다면 폭발시킨다.

6. 다시 구슬이 이동한다. 

7. 5, 6번 과정을 더 이상 구슬 폭발이 일어나지 않을 때까지 반복한다.

8. 이제 번호가 같은 연속되어 나열된 구슬의 개수 A, 구슬의 번호 B를 구하고 A, B를 칸의 1번부터 새로이 집어넣는다.

9. 3~8번 과정을 M번 반복한다.

10. 마지막으로 M번 블리자드 마법을 시전하는 과정에서 폭발된 1번 구슬 + (2 * 폭발된 2번 구슬) + (3 * 폭발된 3번 구슬)의 값을 구한다.

 

여기서 Bead_Number에 담긴 각 칸의 정보를 다시 2차원 배열로 옮겨담았는데, 지금 생각해 보니 그럴 필요가 전혀 없었으며, 오히려 이 과정 때문에 시간이 좀 더 걸렸다. 1차원 배열만을 이용하면 된다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 55
#define LL long long
#define INF 1e9

using namespace std;
int N, M;
int MAP_Number[MAX][MAX]; // (i, j)칸에 적힌 수
int MAP[MAX][MAX]; // (i, j)칸에 있는 구슬의 번호
int Bead_Number[MAX * MAX]; // i번째 칸에 있는 구슬
int tmp[MAX * MAX];
pair<int, int> Shark; // 상어의 위치
bool visited[MAX][MAX];
// 칸의 번호를 매길 때 사용
int moveY[4] = { 0,1,0,-1 };
int moveX[4] = { -1,0,1,0 };
// 블리자드 마법을 시전할 때 사용
int BlizzardY[5] = { 0,-1,1,0,0 };
int BlizzardX[5] = { 0,0,0,-1,1 };
int Bombed_Bead[4] = { 0, }; // i번 구슬이 폭발한 횟수

void init() {
	/*
		격자의 번호를 매기는 함수 구현
	*/
	Shark = make_pair((N + 1) / 2, (N + 1) / 2);
	int Dir = 0;
	int Len = 1;
	int Cnt = 0;
	int Number = 1;
	while (1) {
		for (int i = 0; i < Len; i++) {
			int Y = Shark.first;
			int X = Shark.second;
			int nextY = Y + moveY[Dir];
			int nextX = X + moveX[Dir];
			MAP_Number[nextY][nextX] = Number;
			Number++;
			Shark = make_pair(nextY, nextX);
		}
		Dir++;
		if (Dir == 4) {
			Dir = 0;
		}
		Cnt++;
		if (Cnt == 2) {
			Cnt = 0;
			Len++;
		}
		if (Len == N) {
			for (int i = 0; i < Len; i++) {
				int Y = Shark.first;
				int X = Shark.second;
				int nextY = Y + moveY[Dir];
				int nextX = X + moveX[Dir];
				MAP_Number[nextY][nextX] = Number;
				Number++;
				Shark = make_pair(nextY, nextX);
			}
			break;
		}
	};
	Shark = make_pair((N + 1) / 2, (N + 1) / 2);
}

void Blizzard_Magic(int Dir, int Len) {
	// 블리자드 마법 시전: 방향, 거리에 따라 해당하는 칸에 있는 구슬을 모두 파괴한다.
	int Y = Shark.first;
	int X = Shark.second;
	for (int i = 1; i <= Len; i++) {
		int nextY = Y + BlizzardY[Dir];
		int nextX = X + BlizzardX[Dir];
		MAP[nextY][nextX] = 0;
		Bead_Number[MAP_Number[nextY][nextX]] = 0;
		Y = nextY;
		X = nextX;
	}
}

void Bead_Moving() {
	for (int i = 1; i < (N * N); i++) {
		if (Bead_Number[i] == 0) {
			for (int j = (i + 1); j < (N * N); j++) {
				if (Bead_Number[j] != 0) {
					Bead_Number[i] = Bead_Number[j];
					Bead_Number[j] = 0;
					break;
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			MAP[i][j] = Bead_Number[MAP_Number[i][j]];
		}
	}
}

bool Bead_Explosion() {
	// 4개 이상 연속하는 구슬이 있을 때 폭발이 발생한다.
	bool Flag = false;
	int Start = -1;
	int Len = 0;
	for (int i = 1; i < (N * N); i++) {
		if (Bead_Number[i] == 0) {
			break;
		}
		if (Start == -1) {
			Start = i;
			Len = 1;
		}
		else {
			if (Bead_Number[i] == Bead_Number[Start]) {
				Len++;
			}
			else {
				if (Len >= 4) {
					Flag = true;
					for (int j = Start; j < i; j++) {
						Bombed_Bead[Bead_Number[j]]++;
						Bead_Number[j] = 0;
					}
				}
				Start = i;
				Len = 1;
			}
		}
	}
	if ((Start != -1) && (Len >= 4)) {
		Flag = true;
		for (int i = Start; i < (N * N); i++) {
			Bombed_Bead[Bead_Number[i]]++;
			Bead_Number[i] = 0;
		}
	}
	return Flag;
}

void Make_Group() {
	// 그룹을 만들어, 연속하는 구슬의 개수를 세고 개수 A, 구슬의 번호 B를 구슬의 번호로 넣는다.
	int A = 0;
	int B = -1;
	for (int i = 0; i < (MAX * MAX); i++) {
		tmp[i] = 0;
	}
	int IDX = 1;
	bool isFull = false;
	for (int i = 1; i < (N * N); i++) {
		if (Bead_Number[i] == 0) {
			continue;
		}
		if (B == -1) {
			B = Bead_Number[i];
			A = 1;
		}
		else {
			if (Bead_Number[i] == B) {
				A++;
			}
			else {
				if (!isFull) {
					tmp[IDX++] = A;
				}
				if (IDX == (MAX * MAX)) {
					isFull = true;
				}
				if (!isFull) {
					tmp[IDX++] = B;
				}
				if (IDX == (MAX * MAX)) {
					isFull = true;
				}
				B = Bead_Number[i];
				A = 1;
			}
		}
	}
	if (B != -1) {
		if (!isFull) {
			tmp[IDX++] = A;
		}
		if (IDX == (MAX * MAX)) {
			isFull = true;
		}
		if (!isFull) {
			tmp[IDX++] = B;
		}
	}
	for (int i = 1; i < (N * N); i++) {
		Bead_Number[i] = tmp[i];
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			MAP[i][j] = Bead_Number[MAP_Number[i][j]];
		}
	}
}

int Solution() {
	return (Bombed_Bead[1] + (2 * Bombed_Bead[2]) + (3 * Bombed_Bead[3]));
}

int main() {
	FIRST
	cin >> N >> M;
	init();
	// 현재 격자마다 들어 있는 구슬의 번호 입력
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> MAP[i][j];
			Bead_Number[MAP_Number[i][j]] = MAP[i][j];
		}
	}
	// 상어가 총 M번의 블리자드 마법을 시전
	for (int i = 0; i < M; i++) {
		int D, S;
		cin >> D >> S;
		Blizzard_Magic(D, S);
		Bead_Moving();
		while (1) {
			bool isExplosion = Bead_Explosion();
			Bead_Moving();
			if (!isExplosion) {
				break;
			}
		};
		Make_Group();
	}
	cout << Solution() << "\n";

	return 0;
}

'BOJ > Gold' 카테고리의 다른 글

[BOJ/Gold 2] 백준 20061 모노미노도미노 2(C++)  (0) 2022.01.28
[BOJ/Gold 1] 백준 23290 마법사 상어와 복제(C++)  (0) 2022.01.21
[BOJ/Gold 5] 백준 16234 인구 이동(C++)  (0) 2022.01.19
[BOJ/Gold 2] 백준 17270 연예인은 힘들어(C++)  (0) 2022.01.18
[BOJ/Gold 3] 백준 14890 경사로(C++)  (0) 2022.01.18

티스토리툴바