[Softeer](LV 3) Garage game

문제 링크

LV 3: Garage game

구현 방식

• python으로는 시간초과가 해결이 안돼서 cpp로 풀었다

• dfs 기반의 simulation 문제이다

• dfs에서 2중 for문을 돌면서, backup_board[i][j]가 0이 아니고 [i][j]가 방문한 적이 없는 칸이라면 1)터뜨리기 2)칸 내리기 를 수행해준다

• 만약 turn이 0, 1이라면 1)터뜨리기 수행 후에 2)칸 내리기를 수행해주고 다음 turn 수행을 위해 dfs를 호출해준다. 만약 turn이 2라면 2)칸 내리기를 수행하지 않고 max_score를 update 해준다

코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int board[45][15];
int N;
int max_score = 0;

void dfs(int turn, int score){
	int backup_board[45][15];
	memcpy(backup_board, board, sizeof(board));

	bool visit[15][15] = {false,};
	for (int i=2*N; i<3*N; i++){
		for (int j=0; j<N; j++){
			int flag = backup_board[i][j];
			if (!visit[i-2*N][j] && flag != 0){
				memcpy(board, backup_board, sizeof(backup_board));

				// 터뜨리기
				int minX = i; int maxX = i; int minY = j; int maxY = j;
				queue<pair<int, int>> q; q.push({i, j});
				visit[i-2*N][j] = true;
				int cnt = 1; //터지는 칸의 개수
				while (!q.empty()){
					int x = q.front().first;
					int y = q.front().second;
					q.pop();

					board[x][y] = 0;
					minX = min(minX, x); maxX = max(maxX, x); minY = min(minY, y); maxY = max(maxY, y);
					for (int d=0; d<4; d++){
						int nx = x + dx[d]; int ny = y + dy[d];
						if (2*N<=nx && nx<3*N && 0<=ny && ny<N && !visit[nx-2*N][ny] && backup_board[nx][ny] == flag){
							visit[nx-2*N][ny] = true;
							q.push({nx, ny});
							cnt++;
						}
					}
				}

				// 내리기
				if (turn == 0 || turn == 1){ //첫번째, 두번째 시뮬에서는 내려줌 && 재귀 호출
					for (int x=minX; x<=maxX; x++){
						for (int y=minY; y<=maxY; y++){
							if (board[x][y] == 0){
								int step = 0; //해당 y에서, 몇 x방향으로 몇 칸 내릴 지
								for (int xx=x-1; xx>=0; xx--){
									if (board[xx][y]){
										step = x-xx; break;
									}
								}
								for (int xx=x; xx>=step; xx--){
									board[xx][y] = board[xx-step][y];
									board[xx-step][y] = 0;
								}
							}
						}
					}

					// for (int a=0; a<3*N; a++){
					// 	for (int b=0; b<N; b++){
					// 		cout << board[a][b];
					// 	}
					// 	cout<<'\n';
					// }
					// cout << '\n';

					dfs(turn+1, score+cnt+((maxX-minX+1)*(maxY-minY+1)));
				}
				else{ //세번째 시뮬에서는 내려줄 필요 없이 max_score 갱신
					max_score = max(max_score, score+cnt+((maxX-minX+1)*(maxY-minY+1)));
				}
			}
		}
	}
}

int main(int argc, char** argv)
{
	cin >> N;
	for (int i=0; i<3*N; i++){
		for (int j=0; j<N; j++){
			cin >> board[i][j];
		}
	}
	dfs(0, 0);
	cout << max_score;

	return 0;
}