백준 23290 마법사 상어와 복제

https://www.acmicpc.net/problem/23290

23290번: 마법사 상어와 복제

 

- 구현 + DFS문제이다. 디버깅하느라 정말 힘들었다. 시간 복잡도는 구할 수 없다. 단, 모든 격자에 물고기가 100만마리가 넘지 않도록 입력이 주어지므로, C * 100만 * 명령수 S(maximum 100)해서 시간 초과는 나지 않을 것이다.

 

- 문제에서 주어진 단계들을 하나씩 알아보자.

 

 

1. 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 시간이 조금 걸리기 때문에, 아래 5번에서 물고기가 복제되어 칸에 나타난다.

 

 

- 해당 조건은, 현재 존재하는 모든 물고기들의 정보를 저장해야 한다는 뜻이다. 따라서, 모든 map을 순환하면서, 현재 물고기의 좌표와 dir 정보를 copy_fish 벡터에 담아준다. 이는 5번에서 쓰일 예정이다.

 

 

2. 모든 물고기가 한 칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다. 각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기의 냄새는 아래 3에서 설명한다.

 

 

- 물고기를 이동시키되, 이동할 수 없는 조건을 잘 체크한다. 

 

 

1) 범위 체크

 

2) 물고기 냄새가 있는 칸

  - 후술하겠지만, 물고기가 상어에게 잡아먹힌 경우에 해당 칸에 냄새가 남는다. 이에 대한 정보는 smell 배열에 담겨있다. 

 

3) 상어가 있는 칸

  - shark_x, shark_y와 현재 좌표를 비교

 

 

- 추가적으로, 이 모든 정보는 temp_map에 담아주고, 모든 물고기가 이동을 마쳤을 때 다시 map에 담아주도록 한다. 왜냐하면, map을 순환하며 물고기가 존재할 때 이동을 시켜주도록 구현한다면 이동을 했던 물고기가 또 이동을 해 버리는 문제가 발생하기 때문이다. 예를 들어, (1,1)물고기가 오른쪽 칸으로 이동할 시, (1,2)를 체크하는 과정에서 다시 이동을 해 버리게 된다.

 

 

3. 상어가 연속해서 3칸 이동한다. 

 

 

- 가장 신경을 써야 하는 부분이다. 상어가 움직일 수 있는 경우의 수 중, 가장 많은 물고기를 먹는 경우의 수를 선택해야 한다. 그러한 경우가 여러 개인 경우, 사전순으로 가장 앞서는 방법을 찾아야 한다. 이를 구현하기 위해, move_shark 함수에 string s를 추가하였고, 상어가 이동한 방향에 맞추어 s에 해당 방향을 의미하는 숫자를 더해준다.(to_string 함수 활용) 이 후 상어가 3번을 모두 이동했다면 cnt값이 3일 것이고, 이 때 현재까지 없앤 물고기 수인 fish_num과 현재까지의 임시 답인 answer_fish_num을 비교한다. 만약 fish_num이 더 큰 경우, answer_fish_num을 갱신 해 주어야 한다. 그리고 만약 두 값이 동일한 경우, answer_str과 s를 비교해서 더 사전순로 앞서는 값을 answer_str으로 최신화한다. 

 

- 또한, 먹은 물고기를 계산하는 과정에서, 만약 똑같은 칸을 2번 방문한다면 해당 계산은 무효로 하도록 처리 해 주어야 한다. 이를 위해 visited 배열을 두어서, 만약 똑같은 칸을 두 번째 방문 한 것이라면 s에 해당 방향 추가 및 cnt + 1만 해 주어 함수를 호출하도록 구현 해 준다.

 

- 이 후, 정답 문자열을 활용하여 물고기들을 실제로 map에서 제거하는 remove_fish 함수를 호출한다. 또한 제거함과 동시에 smell 배열에 now_time 변수를 추가 해 준다. 

 

 

4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.

 

 

 

- 필자는 now_time 변수를 활용해서, 매 주문마다 +1이 되도록 하였다. 그리고 물고기가 사라진 시간을 기록하는 smell 변수에 해당 변수를 대입해주었다. 이렇게 하고, remove_smell을 통해 물고기 냄새가 생긴 시간과 현재 시간의 차이가 2인 경우, 해당 칸을 0으로 초기화해주었다.

 

 

5. 1에서 사용한 복제 마법이 완료된다. 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게 된다.

 

 

- 1에서, 모든 물고기의 정보를 저장 해 두었던 copy_fish 벡터에서 요소들을 하나씩 꺼내서, map에 추가를 해 준다.

 

 

 

 

- 디버깅 한 것들

 

 

1. 상어가 이동 시 똑같은 좌표를 재방문하는 경우를 고려하지 못해서, visited 배열을 사용하였다.

 

2. 초기 설계에서, map 벡터에는 방향만 있으면 되는데 x,y좌표를 사용해서 설계를 하는 실수를 했다.

 

3. copy_fish와 temp_map을 매 loop마다 초기화 하는 것을 빠뜨렸었다.

 

 

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
using namespace std;
vector<pair<pair<int, int>, int>> copy_fish;
vector<int> map[5][5];
vector <int> temp_map[5][5];
int shark_x, shark_y, answer_fish_num;
string answer_str;
int smell[5][5];
int dx[] = { 0,-1,-1,-1,0,1,1,1 };
int dy[] = { -1,-1,0,1,1,1,0,-1 };
bool visited[5][5];
int now_time;
void debugging() {
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 0; k < map[i][j].size(); k++) {
				cout << i << " " << j << "좌표의 물고기 dir" << map[i][j][k] << '\n';
			}
		}
	}
	cout << "냄새의 좌표" << '\n';
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			cout << smell[i][j] << " ";
		}
		cout << '\n';
	}
	cout << '\n';
}
void calc_answer() {
	int answer = 0;
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 0; k < map[i][j].size(); k++) answer++;
		}
	}
	cout << answer;
}
void remove_smell() {
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			if (now_time - smell[i][j] == 2) smell[i][j] = 0;
		}
	}
}
void remove_fish(string s) {
	int x = shark_x; int y = shark_y;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '1') {
			x += dx[2]; y += dy[2];
		}
		else if (s[i] == '2') {
			x += dx[0]; y += dy[0];
		}
		else if (s[i] == '3') {
			x += dx[6]; y += dy[6];
		}
		else {
			x += dx[4]; y += dy[4];
		}
		if (!map[x][y].empty()) {
			smell[x][y] = now_time;
			map[x][y].clear();
		}
	}
	shark_x = x; shark_y = y;
}
int calc_dir(int num) {
	if (num == 0) return 2;
	else if (num == 2)return 1;
	else if (num == 4) return 4;
	else return 3;
}
void move_shark(int shark_x, int shark_y, string s, int fish_num, int cnt){
	if (cnt == 3) {
		if (answer_fish_num < fish_num) {
			answer_fish_num = fish_num;
			answer_str = s;
		}
		else if (answer_fish_num == fish_num) {
			answer_str = (answer_str < s) ? answer_str : s;
		}
		return;
	}
	for (int i = 0; i < 8; i+=2) {
		int x = shark_x + dx[i]; int y = shark_y + dy[i];
		if (x < 1 || x > 4 || y < 1 || y > 4) continue;
		int dir = calc_dir(i);
		if(visited[x][y]) move_shark(x, y, s + to_string(dir), fish_num, cnt + 1);
		else {
			visited[x][y] = true;
			move_shark(x, y, s + to_string(dir), fish_num + map[x][y].size(), cnt + 1);
			visited[x][y] = false;
		}
	}
}
void move_temp() {
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 0; k < temp_map[i][j].size(); k++) {
				int dir = temp_map[i][j][k];
				map[i][j].push_back(dir);
			}
		}
	}
}
void clear_vector(int num) {
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			if(!num) map[i][j].clear();
			else temp_map[i][j].clear();
		}
	}
}
void move_fish() {
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 0; k < map[i][j].size(); k++) {
				int dir = map[i][j][k];
				int limit = 0;
				int nx, ny;
				while (1) {
					nx = i + dx[dir]; ny = j + dy[dir];
					if ((nx < 1 || nx > 4 || ny < 1 || ny > 4) || smell[nx][ny] > 0 || (nx == shark_x && ny == shark_y)) {
						dir = (dir == 0) ? 7 : (dir - 1);
						limit++;
					}
					else {
						temp_map[nx][ny].push_back(dir);
						break;
					}
					if (limit > 8) {
						temp_map[i][j].push_back(map[i][j][k]);
						break;
					}
				}
			}
		}
	}
	clear_vector(0);
	move_temp();
	clear_vector(1);
}
void copy_all_fish() {
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 0; k < map[i][j].size(); k++) {
				int dir = map[i][j][k];
				copy_fish.push_back({ {i,j}, dir });
			}
		}
	}
}
void copy_first_fish() {
	for (int i = 0; i < copy_fish.size(); i++) {
		int x = copy_fish[i].first.first;
		int y = copy_fish[i].first.second;
		int dir = copy_fish[i].second;
		map[x][y].push_back(dir);
	}
}
int main() {
	int m, s;
	cin >> m >> s;
	for (int i = 0; i < m; i++) {
		int x, y, dir;
		cin >> x >> y >> dir;
		map[x][y].push_back(dir-1);
	}
	cin >> shark_x >> shark_y;
	while (s--) {
		now_time++;
		answer_str = "999";
		copy_all_fish();
		move_fish();
		move_shark(shark_x, shark_y, "", 0, 0);
		answer_fish_num = 0;
		remove_fish(answer_str);
		remove_smell();
		copy_first_fish();
		memset(visited, false, sizeof(visited));
		copy_fish.clear();
	}
	calc_answer();
	return 0;
}