[백준] 20058-마법사 상어와 파이어스톰(C++)

문제링크: www.acmicpc.net/problem/20058

20058번: 마법사 상어와 파이어스톰

 

삼성 코딩테스트 문제입니다.

구현해야하는 항목이 많아서 번거로운 문제였지만, 구현자체의 난이도는 어려운 문제가 아닙니다.

이런 문제일수록 항목별로 나눠 구현하고 중간중간에 디버깅을 해보면서 정상적으로 동작해야 하는지 확인해야 힙니다.

 

크게 구현할 내용은

 

• 1. 입력값 받기
• 2. 구역 범위 나누기
• 3. 90도 회전시키기
• 4. 얼음 녹이기
• 5. 결과값 도출하기

입니다. 

 

구역 범위는 구획의 크기별로 2중포문을 통해 구현하면 됩니다. 

 

90도 회전은 temp라는 임시배열을 생성하고 해당 배열에 90도 돌려서 옮겨주면 됩니다. 

이때 모든 부분을 90로 회전하기 때문에 len, y, x 값을 줄이며 반복해줍니다.

얼음 녹이기는 4방향을 비교하며 해결하였고

 

결과값 도출시에는 bfs를 사용하여 하나의 덩어리합을 구했습니다.

 

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int arr[100][100] = { 0, };
int temp[100][100] = { 0, };
int visited[100][100] = { 0, };

int n, q;
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };
int result1 = 0, result2 = 0;

void rotate(int sy, int sx, int v) {
	int y = sy;
	int x = sx;
	int len = v;

	while (len > 1) {


		for (int i = y, j = 1; j <= len; j++, i++) {  //1
			temp[y][x + len - j] = arr[i][x];
		}

		for (int i = x, j = 0; j < len; j++, i++) { //2
			temp[y + j][x] = arr[y + len - 1][i];
		}

		for (int i = y + len - 1, j = 0; j < len; j++, i--) {  //3
			temp[y + len - 1][x + j] = arr[i][x + len - 1];
		}


		for (int i = x + len - 1, j = 1; j <= len; j++, i--) { //4
			temp[y + len - j][x + len - 1] = arr[y][i];
		}


		y++;
		x++;
		len -= 2;
	}

}

int bfs(int y, int x, int len) {
	visited[y][x] = 1;
	int result = 1;
	queue <pair <int, int>> que;
	que.push(make_pair(y, x));

	while (!que.empty()) {

		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny >= 1 && ny <= len && nx >= 1 && nx <= len && visited[ny][nx] == 0 && arr[ny][nx] > 0) {
				visited[ny][nx] = 1;
				result++;
				que.push(make_pair(ny, nx));
			}

		}
	}

	return result;

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	//0. input
	cin >> n >> q;
	int len = 1;
	for (int i = 0; i < n; i++)
		len *= 2;
	for (int i = 1; i <= len; i++)
		for (int j = 1; j <= len; j++)
			cin >> arr[i][j];

	for (int k = 0; k < q; k++) {
		int temp1;
		cin >> temp1;
		if (temp1 != 0) { //0이 아닐 때 
			int v = 1;
			for (int i = 0; i < temp1; i++)
				v *= 2;
			//1. divide
			memset(temp, 0, sizeof(temp));
			for (int i = 1; i < len; i += v)
				for (int j = 1; j < len; j += v) {
					//2. rotate
					rotate(i, j, v);
				}
			for (int i = 1; i <= len; i++)
				for (int j = 1; j <= len; j++)
					arr[i][j] = temp[i][j];
		}

		//3. erase ice

		memset(temp, 0, sizeof(temp));

		for (int i = 1; i <= len; i++)
			for (int j = 1; j <= len; j++) {
				temp[i][j] = arr[i][j];
				int zero_ = 0;
				for (int u = 0; u < 4; u++) {
					if (arr[i + y_ar[u]][j + x_ar[u]] != 0)
						zero_++;
				}
				if (zero_ < 3 && arr[i][j] > 0) {
					temp[i][j] --;
				}
			}
		for (int i = 1; i <= len; i++)
			for (int j = 1; j <= len; j++)
				arr[i][j] = temp[i][j];

		/*
		cout << endl;
		for (int i = 1; i <= len; i++) {
		for (int j = 1; j <= len; j++)
		cout << arr[i][j] << ' ';
		cout << endl;
		}*/

	}

	//4. result

	for (int i = 1; i <= len; i++)
		for (int j = 1; j <= len; j++) {
			result1 += arr[i][j];
			if (visited[i][j] == 0 && arr[i][j] > 0)
				result2 = max(result2, bfs(i, j, len));
		}



	cout << result1 << endl;
	cout << result2 << endl;
}