[ SWEA ] 5656. 벽돌 깨기

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

SW Expert Academy

 

풀이 방법

이 문제 역시 구슬을 쏘는 위치의 순서를 모든 경우를 구하여 계산했다. W*H 게임판에서 N번 구슬을 쏘는 경우의 수는 W^N이다. 이때, W의 최대값은 12, N의 최대값은 4이기 때문에 전체 경우의 수는 12^4가지이다.

 

구슬을 쏘는 위치의 순서가 정해졌을 때, 게임을 시뮬레이션하는 함수는 play()이다. 각 슈팅에 대하여 shoot_at() 함수로 구현했다.

int play() {
	...
	for (int i = 0; i < N; i++) {
		// shoot
		shoot_at(shoot[i]);
	}
	...
}

 

shoot_at()

인자로 구슬을 쏘는 위치 w가 주어진다. 해당 column에 대하여 처음으로 벽이 나오는 위치를 스택에 넣는다.

for (int i = 0; i < H; i++) {
	if (copy_map[i][w] > 0) {
		st.push({ i, w });
		visit[i][w] = true;
		break;
	}
}

 

그 후, DFS를 돌면서 연쇄적으로 벽돌을 깬다.  현재 위치의 벽돌을 깬 후, 벽돌의 값 power만큼 상, 하, 좌, 우의 벽돌들을 살펴본다. 만약 벽돌의 power가 1보다 크면 연쇄적으로 벽돌을 깰 수 있기 때문에 스택에 추가한다.

while (!st.empty()) {
	pair<int, int> pos = st.top();
	st.pop();

	int power = copy_map[pos.first][pos.second];
	copy_map[pos.first][pos.second] = 0;
	
	for (int i = 1; i < power; i++) {
		for (int j = 0; j < 4; j++) {
			int next_r = pos.first + i * dr[j];
			int next_c = pos.second + i * dc[j];
			if (valid(next_r, next_c)) {
				if (copy_map[next_r][next_c] > 1) {
					if (!visit[next_r][next_c]) {
						visit[next_r][next_c] = true;
						st.push({ next_r, next_c });
					}
				}
				else if (copy_map[next_r][next_c] == 1) copy_map[next_r][next_c] = 0;
			}
		}
	}
}

이때, 스택에 벽돌이 중복되서 들어갈 수 있기 때문에 visit 배열을 이용해 중복을 방지한다.

 

전체 코드는 여기서 확인할 수 있다.