5656. 벽돌 깨기

static int N, W, H;
static int board[15][12];
static int selected[4];
static int bricks;
static int d[4][2] = {
	-1, 0, //up
	1, 0, //down
	0, -1, //left
	0, 1 //right
};

static bool out_of_bound(int y, int x)
{
	if (y < 0 || y >= H)
		return true;
	if (x < 0 || x >= W)
		return true;
	return false;
}

static int simulation()
{
	int cpy[15][12], ret = 0;
	queue<pair<int, int>> q;
	stack<int> s;

	memcpy(cpy, board, sizeof(board));

	for (int i = 0; i < N; i++)
	{
		int x = selected[i], breaked = 0;
		bool visit[15][12];

		memset(visit, false, sizeof(visit));
		for (int y = 0; y < H; y++) //phase1, find start point
		{
			if (cpy[y][x] > 0)
			{
				q.push({ y, x });
				visit[y][x] = true;
				break;
			}
		}

		while (q.size()) //phase2, bfs
		{
			pair<int, int> cur = q.front();
			q.pop();

			int range = cpy[cur.first][cur.second];
			cpy[cur.first][cur.second] = 0; //breaked
			breaked += 1;

			for (int dir = 0; dir < 4 && range > 1; dir++)
			{
				int y = cur.first, x = cur.second;
				for (int r = 1; r < range; r++) //for all direction,
				{
					y += d[dir][0];
					x += d[dir][1];
					if (out_of_bound(y, x))
						break;
					if (!cpy[y][x]) //이미 깨져있는 곳이라면 패스
						continue;
					if (visit[y][x]) //방문한 정점이라면 패스
						continue;
					
					q.push({ y, x });
					visit[y][x] = true;
				}
			}
		}
		ret += breaked; //깨진 벽돌 개수 누적,

		for (int x = 0; x < W && breaked > 1; x++) //phase3, reconstruct
		{
			for (int y = 0; y < H; y++)
			{
				if (cpy[y][x]) //아직 깨지지 않았다면,
					s.push(cpy[y][x]);
			}
			for (int y = H - 1; y >= 0; y--)
			{
				if (s.size()) //스택에 있는 정보를 먼저 사용
				{
					cpy[y][x] = s.top();
					s.pop();
				}
				else
					cpy[y][x] = 0;
			}
		}
	}
	
	return ret; //총 깨진 개수
}

static int __solution(int turn)
{
	if (turn >= N)
	{
		return simulation();
	}
	else
	{
		int max = 0;
		//구슬을 떨어뜨릴 수 있는 모든 조합을 생성
		for (int x = 0; x < W; x++)
		{
			selected[turn] = x;
			int ret = __solution(turn + 1);
			if (ret > max)
				max = ret;
			if (max == bricks)
				return max;
		}
		return max;
	}
}

static int solution()
{
	scanf("%d %d %d", &N, &W, &H);
	bricks = 0;
	for (int y = 0; y < H; y++)
	{
		for (int x = 0; x < W; x++)
		{
			scanf("%d", &board[y][x]);
			if (board[y][x] > 0)
				bricks += 1;
		}
	}
	return bricks - __solution(0);
}

예전에 풀었던 방법보다 시간이 더 오래 걸렸다.

이에 대해 한차례 정리하자면,

예전에 풀었던 방식은 재귀를 하면서 동시에 시뮬레이션도 같이 진행한다. 그래서 이 경우 불필요한 경우는 필터링 되어 처리하지 않는 경우도 존재한다.

그러나 위에서 한 방식은 일단 벽돌을 떨어뜨릴 위치를 전부 만들어가면서 한번에 시뮬레이션을 진행한다.

이러한 차이로 인해 실행시간이 더 오래걸렸다.

 

먼저 푼 방식을 정리하면,

step1, 벽돌을 떨어뜨릴 위치를 전부 만들어 본다. (중복 조합, a1 + a2 + a3 + ... + a12 = 4)

step2, 첫번째 돌을 정해진 위치에 떨어 뜨릴 시 제일 처음 만나는 벽돌의 y위치를 찾는다.

step3, 해당 벽돌위치를 시작으로 bfs를 시작한다.

step4, bfs시 상,하,좌,우 모든 방향으로 움직이는데, 배열의 범위 밖이면 탈출하는 것이 당연하나, 이미 깨진 곳이나, 이미 방문하여 큐에 들어있는 경우는 탈출하는 것이 아니라 건너 뛰는 것이 맞다. 왜냐하면 그 위치를 지나 더 가면 깨지지 않은 벽돌이 존재할 수 있기 때문이다.

step5, 깨지지 않은 벽돌들을 밑으로 내린다.

 

위 단계에서 빠르게 종료할 수 있거나 굳이 하지 않아도 되는 부분이 있다. 그 부분은 재귀를 빠르게 탈출 시키거나, bfs 시작 시 폭발 반경이 1인 벽돌의 경우에 step5를 하지 않는 것이다.

 

 

//주의사항 및 정리

1. 처음 입력으로 주어진 이차원 배열(board)과 시뮬레이션 하기 위해 이를 복사한 이차원 배열(cpy)이 있을 때, cpy를 사용하여 처리해야하는 코드를 작성해야 하는데, board를 사용하는 코드를 자꾸 작성하는 버릇이 있는 것 같다. 예전에도 이러한 실수를 하여 헤맨 경우가 있다.

2. bfs시 탈출해야는 부분과 해당 좌표를 건너뛰어야 하는 부분을 정확히 파악해야 한다. 코드 실행시간 때문에 너무 성급하게 반복문을 탈출하려고 하는 경향이 있는 것 같은데, 최대한 정확하게 작성하여 샘플 테스트 케이스를 맞추는 것이 먼저고, 실행 시간은 그 다음이어도 늦지 않다.