23290번: 마법사 상어와 복제

첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향

www.acmicpc.net

문제

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

격자에는 물고기 M마리가 있다. 각 물고기는 격자의 칸 하나에 들어가 있으며, 이동 방향을 가지고 있다. 이동 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다. 마법사 상어도 연습을 위해 격자에 들어가있다. 상어도 격자의 한 칸에 들어가있다. 둘 이상의 물고기가 같은 칸에 있을 수도 있으며, 마법사 상어와 물고기가 같은 칸에 있을 수도 있다.

상어의 마법 연습 한 번은 다음과 같은 작업이 순차적으로 이루어진다.

  1. 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 시간이 조금 걸리기 때문에, 아래 5번에서 물고기가 복제되어 칸에 나타난다.
  2. 모든 물고기가 한 칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다. 각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기의 냄새는 아래 3에서 설명한다.
  3. 상어가 연속해서 3칸 이동한다. 상어는 현재 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다. 연속해서 이동하는 칸 중에 격자의 범위를 벗어나는 칸이 있으면, 그 방법은 불가능한 이동 방법이다. 연속해서 이동하는 중에 상어가 물고기가 있는 같은 칸으로 이동하게 된다면, 그 칸에 있는 모든 물고기는 격자에서 제외되며, 제외되는 모든 물고기는 물고기 냄새를 남긴다. 가능한 이동 방법 중에서 제외되는 물고기의 수가 가장 많은 방법으로 이동하며, 그러한 방법이 여러가지인 경우 사전 순으로 가장 앞서는 방법을 이용한다. 사전 순에 대한 문제의 하단 노트에 있다.
  4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
  5. 1에서 사용한 복제 마법이 완료된다. 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게 된다.

격자에 있는 물고기의 위치, 방향 정보와 상어의 위치, 그리고 연습 횟수 S가 주어진다. S번 연습을 모두 마쳤을때, 격자에 있는 물고기의 수를 구해보자.

입력

첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향은 8 이하의 자연수로 표현하고, 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 마지막 줄에는 sx, sy가 주어지며, 상어가 (sx, sy)에 있음을 의미한다.

격자 위에 있는 물고기의 수가 항상 1,000,000 이하인 입력만 주어진다.

출력

S번의 연습을 마친 후 격자에 있는 물고기의 수를 출력한다.

제한

  • 1 ≤ M ≤ 10
  • 1 ≤ S ≤ 100
  • 1 ≤ fx, fy, sx, sy ≤ 4
  • 1 ≤ d ≤ 8
  • 두 물고기 또는 물고기와 상어가 같은 칸에 있을 수도 있다.

예제 입력 1

5 1
4 3 5
1 3 5
2 4 2
2 1 6
3 4 4
4 2

예제 출력 1

9

격자의 초기 상태는 다음 그림과 같다. 상어가 있는 칸은 배경색이 어두운 칸, 물고기는 방향으로 표시했다.

물고기가 한 칸 이동하면 다음과 같다.

상어는 [상, 상, 상]으로 이동한다. 이때 (3, 2)에 있는 물고기가 격자에서 제외된다. 물고기의 냄새가 있는 칸은 배경의 색이 빨간색이다.

이제 복제 마법이 완료된다.

예제 입력 2

5 2
4 3 5
1 3 5
2 4 2
2 1 6
3 4 4
4 2

예제 출력 2

13

예제 1의 상태에서 연습을 한 번 더 해야 한다. 물고기가 한 칸 이동하면 다음 그림과 같다.

상어는 [우, 우, 하]로 이동한다. (2, 4)에도 상어의 냄새가 있으나 상어의 위치와 겹쳐 그림에는 표시하지 않았다.

아직 격자에서 사라질 냄새는 없다. 복제 마법이 완료되면 다음과 같다.

예제 입력 3

5 3
4 3 5
1 3 5
2 4 2
2 1 6
3 4 4
4 2

예제 출력 3

17

예제 2의 상태에서 연습을 한 번 더 해야 한다. 물고기가 한 칸 이동하면 다음과 같다.

상어는 [좌, 좌, 상]으로 이동한다. 여기서 9마리의 물고기가 격자에서 제외된다. 첫 번째 연습에서 생긴 냄새가 격자에서 사라진다. 상어가 있는 칸에는 어두운 배경 대신 상어를 표시했다.

복제 마법이 완료되면 격자의 상태는 아래 그림과 같아진다.

예제 입력 4

5 5
4 3 5
1 3 5
2 4 2
2 1 6
3 4 4
4 2

예제 출력 4

35

예제 입력 5

5 26
4 3 5
1 3 5
2 4 2
2 1 6
3 4 4
4 2

예제 출력 5

640240

예제 입력 6

1 10
1 1 1
4 4

예제 출력 6

26

예제 입력 7

8 100
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1

예제 출력 7

8

예제 입력 8

10 25
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
2 1 1
2 1 1
2 1

예제 출력 8

574418

노트

상어의 이동 방법 중 사전 순으로 가장 앞서는 방법을 찾으려면 먼저, 방향을 정수로 변환해야 한다. 상은 1, 좌는 2, 하는 3, 우는 4로 변환한다. 변환을 모두 마쳤으면, 수를 이어 붙여 정수로 하나 만든다. 두 방법 A와 B가 있고, 각각을 정수로 변환한 값을 a와 b라고 하자. a < b를 만족하면 A가 B보다 사전 순으로 앞선 것이다.

예를 들어, [상, 하, 좌]를 정수로 변환하면 132가 되고, [하, 우, 하]를 변환하면 343이 된다. 132 < 343이기 때문에, [상, 하, 좌]가 [하, 우, 하]보다 사전 순으로 앞선다.

총 43 = 64가지 방법을 사전 순으로 나열해보면 [상, 상, 상], [상, 상, 좌], [상, 상, 하], [상, 상, 우], [상, 좌, 상], [상, 좌, 좌], [상, 좌, 하], [상, 좌, 우], [상, 하, 상], ..., [우, 하, 하], [우, 하, 우], [우, 우, 상], [우, 우, 좌], [우, 우, 하], [우, 우, 우] 이다.


알고리즘 분류

  • 구현
  • 시뮬레이션
  • 백트래킹

풀이

블리자드는 2시간을 투자했지만 복제는 4시간을 썼는데도 안 풀려서 얍문 형님의 블로그를 참고하였다.

https://yabmoons.tistory.com/719

 

[ 백준 23290 ] 마법사 상어와 복제 (C++)

백준의 마법사 상어와 복제(23290) 문제이다. [ 문제 바로가기 ] [ 문제풀이 ] 주어진 문제에 맞게 진행했을 때 최종적으로 물고기가 격자에 몇 마리가 남아있는지 구해야 하는 문제이다. (이 글을

yabmoons.tistory.com

1. 우선 물고기의 정보를 입력받으면, (FY, FX)번째 벡터에 물고기의 정보를 push한다.

2. 복제를 위한 임시 벡터 배열을 현재 격자로 초기화한다.

3. 격자의 각 칸마다 있는 물고기들을 이동시키며, 여기서 격자를 벗어나거나 상어를 만나거나 냄새가 있는 곳이라면 반시계 방향 45도 회전한 후 다시 확인한다. 8방향 다 확인했는데 이동할 곳이 없다면 이동시키지 않는다.

4. 백트래킹을 사용하여 상어의 경로를 찾는다. 이 때, (상, 상, 상)부터 순차적으로 확인하기 때문에 사전 순대로 라는 표현을 신경쓰지 않아도 된다.

5. 상어의 경로를 찾았으면 경로대로 움직이면서 물고기를 잡고 냄새를 남긴다.

6. 냄새를 확인하여 현재 턴과 칸에 냄새가 남겨진 턴의 차이가 2라면 냄새를 없앤다.

7. 복제를 위한 임시 벡터 배열에 담겨진 물고기들을 Fish 벡터 배열의 해당하는 칸에 push한다.

8. 2~7번 과정을 S번 반복한 후, 현재 존재하는 물고기들의 수를 구한다.

코드

#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 4
#define LL long long
#define INF 1e9

using namespace std;
struct FISH {
	int FY, FX, D;
};

int M, S;
vector<FISH> Fish_Map[MAX][MAX]; // 현재 격자의 상태. i행 j열의 칸에 있는 물고기들의 정보가 들어 있다.
vector<FISH> Clone_Map[MAX][MAX]; // 복제 마법을 시전하기 위해 필요한 임시 격자
pair<int, int> Shark; // 상어의 위치
int Smell[MAX][MAX]; // i행 j열에 있는 물고기의 냄새
int Tmp_Route[3];
int Shark_Route[3]; // 상어의 이동 경로
int Max_Deleted_Fish; // 상어가 최대로 잡을 수 있는 물고기
// 물고기들의 이동 방향
int Fish_moveY[9] = { 0,0,-1,-1,-1,0,1,1,1 };
int Fish_moveX[9] = { 0,-1,-1,0,1,1,1,0,-1 };
// 상어의 이동 방향
int Shark_moveY[5] = { 0,-1,0,1,0 };
int Shark_moveX[5] = { 0,0,-1,0,1 };

void Copy_Magic() {
	// 1. 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 시간이 조금 걸리기 때문에, 아래 5번에서 물고기가 복제되어 칸에 나타난다.
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			Clone_Map[i][j] = Fish_Map[i][j];
		}
	}
}

bool isShark(int Y, int X) {
	// 물고기가 이동하는 곳이 상어가 있는 곳이라면 false, 그게 아니면 true
	if ((Y == Shark.first) && (X == Shark.second)) {
		return false;
	}
	return true;
}

void Fish_Moving() {
	/*
		2. 모든 물고기가 한 칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다. 
		각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 
		만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 
		그 외의 경우에는 그 칸으로 이동을 한다. 물고기의 냄새는 아래 3에서 설명한다.
	*/
	vector<FISH> Tmp_Map[MAX][MAX]; // 이동한 물고기들의 정보를 담아두는 벡터 배열
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			for (int k = 0; k < Fish_Map[i][j].size(); k++) {
				// i행 j열에 있는 k번째 물고기의 이동 경로를 정할 것이다.
				int Y = Fish_Map[i][j][k].FY;
				int X = Fish_Map[i][j][k].FX;
				int Dir = Fish_Map[i][j][k].D;
				int nextY, nextX;
				bool Flag = false;
				for (int l = 0; l < 8; l++) { // 8방향을 반시계 방향으로 돌리며 확인하면서, 물고기가 갈 수 있는 곳을 찾는다.
					nextY = Y + Fish_moveY[Dir];
					nextX = X + Fish_moveX[Dir];
					if ((nextY >= 0) && (nextY < MAX) && (nextX >= 0) && (nextX < MAX) && (isShark(nextY, nextX)) && (Smell[nextY][nextX] == 0)) {
						Flag = true;
						break;
					}
					Dir--;
					if (Dir == 0) {
						Dir = 8;
					}
				}
				if (Flag) {
					Tmp_Map[nextY][nextX].push_back({ nextY,nextX,Dir });
				}
				else {
					Tmp_Map[Y][X].push_back({ Y,X,Dir });
				}
			}
		}
	}
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			Fish_Map[i][j] = Tmp_Map[i][j];
		}
	}
}

int Shark_Moving_Simulation() {
	bool visited[MAX][MAX] = { false, };
	int Y = Shark.first;
	int X = Shark.second;
	int res = 0;
	for (int i = 0; i < 3; i++) { // 첫 번째부터 세 번째까지의 상어가 선택한 경로
		int Dir = Tmp_Route[i];
		int nextY = Y + Shark_moveY[Dir];
		int nextX = X + Shark_moveX[Dir];
		if ((nextY >= 0) && (nextY < MAX) && (nextX >= 0) && (nextX < MAX)) { // 격자를 벗어나면 안 된다.
			if (!visited[nextY][nextX]) {
				visited[nextY][nextX] = true;
				res += Fish_Map[nextY][nextX].size();
			}
			Y = nextY;
			X = nextX;
		}
		else {
			return -1; // 격자를 벗어나면 -1 return
		}
	}
	return res; // 상어가 잡을 수 있는 물고기의 수의 합 return
}

void Find_Route(int Depth) {
	// 백트래킹 기법을 사용하여 상어의 경로를 찾는다.
	if (Depth == 3) {
		int Ate = Shark_Moving_Simulation();
		if (Max_Deleted_Fish < Ate) {
			Max_Deleted_Fish = Ate;
			for (int i = 0; i < 3; i++) {
				Shark_Route[i] = Tmp_Route[i];
			}
		}
		return;
	}
	for (int i = 1; i <= 4; i++) {
		Tmp_Route[Depth] = i;
		Find_Route(Depth + 1);
		Tmp_Route[Depth] = 0;
	}
}

void Shark_Moving(int Time) {
	/*
		3. 상어가 연속해서 3칸 이동한다. 상어는 현재 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다. 
		연속해서 이동하는 칸 중에 격자의 범위를 벗어나는 칸이 있으면, 그 방법은 불가능한 이동 방법이다. 
		연속해서 이동하는 중에 상어가 물고기가 있는 같은 칸으로 이동하게 된다면, 그 칸에 있는 모든 물고기는 격자에서 제외되며, 
		제외되는 모든 물고기는 물고기 냄새를 남긴다. 
		가능한 이동 방법 중에서 제외되는 물고기의 수가 가장 많은 방법으로 이동하며, 
		그러한 방법이 여러가지인 경우 사전 순으로 가장 앞서는 방법을 이용한다.
	*/
	vector<FISH> Tmp_Map[MAX][MAX];
	Max_Deleted_Fish = -1;
	Find_Route(0);
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			Tmp_Map[i][j] = Fish_Map[i][j];
		}
	}
	int Y = Shark.first;
	int X = Shark.second;
	for (int i = 0; i < 3; i++) { // 상어의 이동 경로를 정한 후
		int Dir = Shark_Route[i];
		int nextY = Y + Shark_moveY[Dir];
		int nextX = X + Shark_moveX[Dir];
		if (Tmp_Map[nextY][nextX].size() != 0) { // 물고기가 있는 곳이라면 물고기를 다 잡으면서, 물고기는 칸에 냄새를 남긴다.
			Smell[nextY][nextX] = Time;
			Tmp_Map[nextY][nextX].clear();
		}
		Y = nextY;
		X = nextX;
		Shark.first = Y;
		Shark.second = X;
	}
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			Fish_Map[i][j] = Tmp_Map[i][j];
		}
	}
}

void Smell_Delete(int Time) {
	// 4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			if (Smell[i][j] > 0) {
				if (Time - Smell[i][j] == 2) { // 현재 턴과 칸에 냄새가 남겨진 턴의 차이가 2라면 냄새는 사라진다.
					Smell[i][j] = 0;
				}
			}
		}
	}
}

void Finish_Magic() {
	// 5. 1에서 사용한 복제 마법이 완료된다. 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게 된다.
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			for (int k = 0; k < Clone_Map[i][j].size(); k++) {
				Fish_Map[i][j].push_back(Clone_Map[i][j][k]);
			}
		}
	}
}

int Fish_Counting() {
	int res = 0;
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			res += Fish_Map[i][j].size();
		}
	}
	return res;
}

int main() {
	FIRST
	cin >> M >> S;
	for (int i = 0; i < M; i++) {
		int FY, FX, D;
		cin >> FY >> FX >> D;
		FY--;
		FX--;
		Fish_Map[FY][FX].push_back({ FY,FX,D });
	}
	cin >> Shark.first >> Shark.second;
	Shark.first--;
	Shark.second--;
	for (int i = 1; i <= S; i++) {
		Copy_Magic();
		Fish_Moving();
		Shark_Moving(i);
		Smell_Delete(i);
		Finish_Magic();
	}
	cout << Fish_Counting() << "\n";

	return 0;
}

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

[BOJ/Gold 5] 백준 2251 물통(C++)  (0) 2022.02.05
[BOJ/Gold 2] 백준 20061 모노미노도미노 2(C++)  (0) 2022.01.28
[BOJ/Gold 1] 백준 21611 마법사 상어와 블리자드(C++)  (0) 2022.01.20
[BOJ/Gold 5] 백준 16234 인구 이동(C++)  (0) 2022.01.19
[BOJ/Gold 2] 백준 17270 연예인은 힘들어(C++)  (0) 2022.01.18

티스토리툴바