[백준] 21609번 상어 중학교 [C++]

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

21609번: 상어 중학교

친구가 빨리풀기 대결하자고 해서 언어를 맞추기위해 오랜만에 C++로 풀었다.

최근 삼성 역량테스트 문제다. 그래서 구현이 조금 까다롭지만 시키는대로 잘 하면 된다. 이런 문제를 많이 풀어보는 게 삼성 역량테스트에서 중요한 것 같다.

 

메인함수부터 순서대로 설명하면 이렇다.

조건에 해당하는 블럭이 있을 경우(loop==true) 반복한다.

 

블럭 묶음의 갯수를 파악하기 위해 dfs함수를 호출했다. 0(무지개색 블럭)은 검은 블럭을 제외한 다른 블럭들이 모두 탐색할 수 있어야하므로 탐색을 위한 방문 배열을 visited로 했고, 같은 블럭 묶음이 탐색되는 중복 계산을 피하기 위해 visited2를 두었다. 

 

dfs가 호출될 때마다 candi_cnt 값이 하나씩 올라가서 블럭의 묶음 개수가 저장된다.

기존 블럭의 묶음 중 가장 큰 블럭 묶음을 cnt에 저장하면서 그 기준 위치를 갱신해간다. 

그리고 그 묶음의 개수가 같다면 .....(생략) (문제의 조건대로 if - else if를 남발해서 구현했다.)

 

 

모든 블럭묶음을 확인 했으면 지워져야 할 블럭의 기준위치가 나온다.

기준 위치에 대한 erase 실시 => drop 실시 => rotate실시 => drop 실시를 한다.

 

erase시 다시 dfs로 기준위치부터 블럭을 지워나갔다 (board 값을 -2로 셋팅)

drop시 시키는대로 drop 했다.

rotate도 시키는대로 했다.

 

내가 친구보다 빨리 풀었다

승리 굳

 

+ 내가 종이랑 펜을 썼기 때문에 친구가 30분 더 풀기로 했으나 최종 승리했다

#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

int board[20][20];
int cnt;
int candi_cnt;
int gijoon_y, gijoon_x;
bool visited[20][20];
bool visited2[20][20];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int N, M;
int cur_block;
int candi_rainbow;
int rainbow;


bool is_boundry(int y, int x) {
	if (y < 0 || x < 0 || y >= N || x >= N) return false;
	return true;
}

void dfs(int y, int x) {
	if (board[y][x] != 0) {
		visited2[y][x] = true;
	}
	candi_cnt++;
	if (board[y][x] == 0) {
		candi_rainbow++;
	}
	for (int i = 0; i < 4; i++) {
		int ny = y + dir[i][0];
		int nx = x + dir[i][1];
		if (!is_boundry(ny, nx) || visited[ny][nx]) continue;
		if (board[ny][nx] == -2 || board[ny][nx] == -1) continue;
		if(!(board[ny][nx] == 0 || board[ny][nx] == cur_block)) continue;
		
		visited[ny][nx] = true;
		dfs(ny, nx);
	}
}

void erase(int y, int x) {
	board[y][x] = -2;
	for (int i = 0; i < 4; i++) {
		int ny = y + dir[i][0];
		int nx = x + dir[i][1];
		if (!is_boundry(ny, nx) || visited[ny][nx]) continue;
		if (board[ny][nx] == -2 || board[ny][nx] == -1 || !(board[ny][nx] == 0 || board[ny][nx] == cur_block)) continue;
		visited[ny][nx] = true;
		erase(ny, nx);
	}
}

void down() {
	for (int i = N - 1; i > 0; i--) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == -2) {
				int y = i - 1;
				while (y>=0 && board[y][j] ==-2) {
					y--;
				}
				if (y >= 0 && board[y][j] != -1) {
					board[i][j] = board[y][j];
					board[y][j] = -2;
				}
			}
		}
	}
}

void rotate() {
	int copy[20][20];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			copy[i][j] = board[j][N - i - 1];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			board[i][j] = copy[i][j];
		}
	}
}

int main(){
	int ans = 0;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}
	gijoon_y = -1;
	gijoon_x = -1;
	bool loop = true;
	while (loop) {
		loop = false;
		cnt = 0;
		rainbow = 0;
		memset(visited, false, sizeof(visited));
		memset(visited2, false, sizeof(visited2));
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visited2[i][j] || board[i][j]==-2) continue;
				if (board[i][j] != -1 && board[i][j] != 0) {
					candi_rainbow = 0;
					candi_cnt = 0;
					cur_block = board[i][j];
					memset(visited, false, sizeof(visited));
					visited[i][j] = true;
					dfs(i, j);
					
					if (candi_cnt < 2) continue;
					loop = true;

					if (candi_cnt > cnt) {
						rainbow = candi_rainbow;
						gijoon_y = i;
						gijoon_x = j;
						cnt = candi_cnt;
					}
					else if (candi_cnt == cnt) {
						if (candi_rainbow >= rainbow) {
							rainbow = candi_rainbow;
							gijoon_y = i;
							gijoon_x = j;
						}
					}
					
				}
			}
		}
		memset(visited, false, sizeof(visited));
		if (loop) {
			visited[gijoon_y][gijoon_x] = true;
			cur_block = board[gijoon_y][gijoon_x];
			erase(gijoon_y, gijoon_x);
			ans += cnt * cnt;
			down();
			rotate();
			down();
		}
	}
	cout << ans;
	
}