백준 21610 마법사 상어와 비바라기

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

21610번: 마법사 상어와 비바라기

 

- 상대적으로 쉬운 난이도의 구현 문제이다. 시간복잡도는 O(mN^2)이다. 

 

- cloud_xy에 주어진 4 칸의 좌표를 담고, 총 m번의 이동을 시작한다. 

 

1. 구름 이동의 경우, 1번 행(열)과 n번 행(열)이 연결되어 있는 점을 잘 고려해서 구현한다. 필자는 주어진 방향대로 한 칸씩 이동하도록 하되, 처음 s를 입력받을 때 s=s%n을 해 줌으로써 이동 횟수를 최소화해주었다.  이동할 때 마다 범위를 벗어나는지 체크를 하고(좌표가 0 미만, n이상인 경우) 수정을 해 주었다.

  또한 여기서, cloud가 해당 칸에 존재하는 여부를 담은 2차원 배열 cloud를 false로 초기화 해 주어야 한다. 그래야 다음 로직에서 겹치는 문제가 발생하지 않는다.

 

2. 각 구름에서 비를 내리게 해서 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가하도록 한다.

 

3. 구름이 사라지는 부분은 따로 구현하지 않는다.

 

4. 물복사 버그를 진행한다. 대각선을 체크하되, 1번과 다르게 범위를 벗어나는 경우는 대각선으로 계산하지 않는다.

 

5. 모든 칸을 순회하면서, 물의 양이 2 이상인 칸에 구름을 만든다. 이 때, 이전에 구름이 있던 곳은 pass한다.(cloud 배열 값 활용)

 

- 이 문제는 1시간 내에는 풀어야 코딩테스트를 통과할 수 있을 것 같다!

#include <iostream>
#include <vector>
using namespace std;
int n, m;
int map[50][50];
bool cloud[50][50];
vector<pair<int, int>> cloud_xy;
vector<pair<int, int>> dir_move;
int dx[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int dy[] = { -1,-1,0,1,1,1,0,-1 };
void debugging() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << map[i][j] << ' ';
		}
		cout << '\n';
	}
	cout << '\n';
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		dir_move.push_back({ x, y%n });
	}
	for (int i = n - 2; i < n; i++) {
		for (int j = 0; j < 2; j++) {
			cloud_xy.push_back({ i,j });
		}
	}
	while (m--) {
		int dir = dir_move[0].first-1; int move = dir_move[0].second;
		dir_move.erase(dir_move.begin());
		// 구름 이동
		int now_cloud_size = cloud_xy.size();
		for (int i = 0; i < now_cloud_size; i++) cloud[cloud_xy[i].first][cloud_xy[i].second] = false;
		for (int i = 0; i < now_cloud_size; i++) {
			int nx = cloud_xy[i].first;
			int ny = cloud_xy[i].second;
			for (int j = 0; j < move; j++) {
				nx += dx[dir]; ny += dy[dir];
				if (nx == -1) nx = n - 1; if (ny == -1) ny = n - 1;
				if (nx == n) nx = 0; if (ny == n) ny = 0;
			}
			cloud_xy.push_back({ nx, ny });
			map[nx][ny]++;
			cloud[nx][ny] = true;
		}
		for (int i = 0; i < now_cloud_size; i++) cloud_xy.erase(cloud_xy.begin());
        // 물복사 버그
		for (int i = 0; i < cloud_xy.size(); i++) {
			int count = 0;
			int now_x = cloud_xy[i].first; int now_y = cloud_xy[i].second;
			for (int j = 1; j < 8; j+=2) {
				int nx = now_x + dx[j]; int ny = now_y + dy[j];
				if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				if (map[nx][ny]) count++;
			}
			map[now_x][now_y] += count;
		}
        // 구름 생성 및 물의 양 -2
		vector<pair<int, int>> temp_cloud;
		for (int i = 0; i < cloud_xy.size(); i++) temp_cloud.push_back({ cloud_xy[i].first, cloud_xy[i].second });
		cloud_xy.clear();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!cloud[i][j] && map[i][j] >= 2) {
					cloud_xy.push_back({ i,j });
					cloud[i][j] = true;
					map[i][j] -= 2;
				}
			}
		}
		for (int i = 0; i < temp_cloud.size(); i++) {
			cloud[temp_cloud[i].first][temp_cloud[i].second] = false;
		}
	}
	int answer = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			answer += map[i][j];
		}
	}
	cout << answer;
	return 0;
}