백준_삼성 역량 기출문제_20058_마법사 상어와 파이어스톰

[youbeen2798]

문제 링크 : https://www.acmicpc.net/problem/20058
문제 난이도 : 골4

문제 조건

• 복잡하므로, 문제 링크로 보는 것을 추천

입력

• 첫째 줄에 N과 Q가 주어짐
• 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어짐
• r번째 줄에서 c번째 주어지는 정수는 A[r][c]
• 마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, …, LQ가 순서대로 주어짐

출력

• 첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력
• 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력

풀이

• 삼성 코딩테스트에서 자주 등장하는 2차원 배열 속 시뮬레이션 문제
• 해당 문제는 3개를 구하는 것으로 나눌수 있다!

1. 격자의 시계방향 회전
2. 얼음의 융해
3. 가장 큰 덩어리 찾기

• 3개 중 가장 난이도가 높은 것은 격자의 시계방향 회전
• 자주 나오기도 하고, 매번 구현하는 것은 시간 낭비이므로 외워두는 것이 좋다
• 얼음의 융해는 단순한 구현이지만, 한 가지 주의해야 할 점이 있다. 얼음은 바로바로 융해하면 안 되고, 한 꺼번에 융해해야 한다는 점이다. 따라서, 얼음이 융해가 되는지 안 되는지를 먼저 전체적으로 체크를 한 후, 나중에 한꺼번에 얼음을 융해시켜야 한다.
• 가장 큰 덩어리 찾기는 정말 단순한 dfs문제이다.

코드

#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;

int n, q;
int board[64][64];
int temp[64][64];

bool checkmelt[64][64];
bool visited[64][64];

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

int answer = 0;
int temp_answer = 0;

void rotate(int x, int y, int num) {

	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			temp[i][j] = board[x + num - 1 - j][y + i];
		}
	}

	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			board[x + i][y + j] = temp[i][j];
		}
	}
}

void solve(int num) {

    num = pow(2, num); //2

	//모든 격자 회전
	for (int i = 0; i < n; i += num) {
		for (int j = 0; j < n; j += num) {
			rotate(i, j, num);
		}
	}

	memset(checkmelt, false, sizeof(checkmelt));

	//용해
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
            
			if (board[i][j] == 0) { //용해시킬 얼음이 없으므로
				continue;
			}

			int cnt = 0;
            
			for (int t = 0; t < 4; t++) {
				int nx = i + dx[t];
				int ny = j + dy[t];

				if (0 <= nx && nx < n && 0 <= ny && ny < n) {
					if (board[nx][ny] > 0) {
						cnt++;
					}
				}
			}

			if (cnt < 3) {
				checkmelt[i][j] = true;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (checkmelt[i][j]) { //용해시키기 위해
				board[i][j]--; //얼음의 수 하나 감소
			}
		}
	}
}


void input() { //입력받기
	cin >> n >> q; //3

	n = pow(2, n); //8

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
		}
	}

	for (int i = 0; i < q; i++) {
		int num;
		cin >> num; //1

		solve(num);
	}
}




void dfs(int x, int y) {

	visited[x][y] = true;
	temp_answer++;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (0 <= nx && nx < n && 0 <= ny && ny < n) {
			if (board[nx][ny] > 0 && visited[nx][ny] == false) {
				dfs(nx, ny);
			}
		}
	}
}

int getsum() {

	int sum = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sum += board[i][j];
		}
	}

	return sum;
}

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

	input(); //입력

	memset(visited, false, sizeof(visited));

	cout << getsum() << "\n";

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (board[i][j] > 0 && visited[i][j] == false) {
				temp_answer = 0;
				dfs(i, j);
				answer = max(temp_answer, answer);
			}
		}
	}

	cout << answer;
}

​

[ghdcksgml1]

굳굳 코드도 깔끔하네~

[youbeen2798]

ㅎㅎ떙큐