5656. [모의 SW 역량테스트] 벽돌 깨기

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

SW Expert Academy

 

DFS + BFS에서 시간초과 발생했고 결과도 이상하게 나왔는데 생각해보니 중력처리가 잘못된거 같다 

빈공간이 발생했을 때 하나만 발생한다고 가정하고 밑으로 땡기는 로직이 허접했다.

연쇄 폭파로 길게  일렬로 발생한 폭파가 옆에서 밑으로 폭파하며 타고 내려가서 그 옆의 아랫부분을 폭파시킬수 있음.

그러면 위 아래로도 구멍이 날 수 있다.

따라서 queue에 값을 담고 열을 싹 비워준다음에 다시 밑에서부터 차곡차곡 올려주면 됨.

그리고 BFS에서도 결과가 잘못됐었던 거 같음 지금 생각해보면...

그리고 중요한건 중력처리시나 queue를 생성할 때 자료구조의 반복 생성은 엄청난 시간을 소비한 다는 것을 알았다.

 

매번 비워지는 queue라면 전역으로 선언할 것!

 

#include<iostream>
#include<string.h>
#include<queue>
#include<vector>

using namespace std;


int N, H, W;
int arr[15][12];
int temp[15][12];
int result = 987654321;
vector<int> ball;
queue<int> que;

void crash(int y, int x)
{
	int val = temp[y][x];
	temp[y][x] = 0;
	for (int i = 1; i < val; i++)
	{
		if (y + i < H && temp[y+i][x])
		{
			crash(y + i, x);
		}
		if (y - i >= 0 && temp[y-i][x])
		{
			crash(y - i, x);
		}
		if (x + i < W && temp[y][x+i])
		{
			crash(y, x + i);
		}
		if (x - i >= 0 && temp[y][x-i])
		{
			crash(y, x - i);
		}
	}

	return;
}

void reset()
{
	int cost = 0;
	int idx = H-1;
	
	for (int j = 0; j < W; j++)
	{
			for (int i = H - 1; i >= 0; i--)
			{
				if (temp[i][j])
				{
					que.push(temp[i][j]);
					temp[i][j] = 0;
				}
			}

			idx = H - 1;
			while (!que.empty())
			{
				cost = que.front();
				que.pop();

				temp[idx][j] = cost;
				idx--;
			}
		
	}
    
}

void DFS(int cur, int num)
{
	if (num == N)
	{

		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				temp[i][j] = arr[i][j];
			}
		}

		for (int i = 0; i < ball.size(); i++)
		{
			for (int j = 0; j < H; j++)
			{
				if (temp[j][ball[i]])
				{
					
					crash(j, ball[i]);
					break;
				}
			}

			reset();


			
		}

		int count = 0;

		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				if (temp[i][j])
				{
					count++;
				}
			}
		}

		if (result > count)
		{
			result = count;
		}
		return;
	}


	for (int i = 0; i < W; i++)
	{
		ball.push_back(i);
		DFS(i, num + 1);
		ball.pop_back();
	}

}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		
		cin >> N >> W >> H;
		result = 987654321;
		ball.clear();

		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				cin >> arr[i][j];
			}
		}

		for (int i = 0; i < W; i++)
		{
			ball.push_back(i);
			DFS(i,1);
			ball.pop_back();
			
		}

		cout << "#" << test_case << " " << result << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}