728x90
dfs와 bfs를 활용하여 문제를 풀었다.
dfs는 벽돌 깨기를 진행하는 과정을, bfs는 특정 벽돌을 깨뜨렸을 때의 연쇄 작용을 구현하기 위해 사용했다.
벽돌 깨기의 경우 한 번 깬 벽돌의 column에 대해서도 다시 벽돌을 깰 수 있으니 방문 여부를 저장할 필요가 없다.
// col에 따라 벽돌깨기 진행
for (int i = 0; i < W; i++)
dfs(i, 0);
dfs는 N번 진행하기 때문에 N이 되었을 때 남은 벽돌 수를 세어서 ans와 비교하였다.
그리고 세로줄 (column)에 대해 벽돌을 깨야 하니까 i열에 대해 map[r][i]가 0이 아닌 경우에 벽돌 깨기 (game)을 진행했다.
static void dfs(int i, int depth) {
if (depth == N) {
int cnt = 0;
for (int r = 0; r < H; r++)
for (int c = 0; c < W; c++)
if (map[r][c] != 0)
cnt++;
ans = Math.min(ans, cnt);
return;
}
for (int r = 0; r < H; r++)
if (map[r][i] != 0) {
game(r, i, depth);
break;
}
}
N번 게임을 수행하기 전에 모든 map이 0으로 채워졌을 경우에는 ans가 업데이트되지 않는데, 그 경우에 main에서 값이 Integer.max_value이면 0으로 바꿨다.
if (ans == Integer.MAX_VALUE)
ans = 0;
System.out.println("#" + t + " " + ans);
game의 과정은 다음과 같다.
- 연쇄적으로 벽돌을 깨뜨리는 과정
연쇄적으로 벽돌을 깨뜨리기 위해 queue를 사용하였다.
val-1만큼 사방탐색을 하고 해당 값이 0보다 크면 배열의 인덱스와 값을 queue에 넣어주고 0으로 바꿔주었다.
static void game(int r, int c, int depth) {
// bfs
Queue<int[]> q = new LinkedList<>();
q.add(new int[] { r, c, map[r][c] });
int[][] copy = new int[H][W];
for (int i = 0; i < H; i++)
copy[i] = map[i].clone(); // 원래 배열 저장
while (!q.isEmpty()) {
int[] tmp = q.poll();
int tmpr = tmp[0];
int tmpc = tmp[1];
int val = tmp[2];
map[tmpr][tmpc] = 0;
label: for (int d = 0; d < 4; d++)
for (int v = 1; v < val; v++) {
int nr = tmpr + dr[d] * v;
int nc = tmpc + dc[d] * v;
if (nr < 0 || nr >= H || nc < 0 || nc >= W)
continue label;
if (map[nr][nc] > 0) {
q.add(new int[] { nr, nc, map[nr][nc] });
map[nr][nc] = 0;
}
}
}
}
- 빈 공간을 채우는 과정
2048에서 구현했던 것처럼 0이 있으면 0이 아닌 원소를 찾아서 해당 값으로 바꾸고, 0이 아닌 원소는 0으로 만든다.
for (int col = 0; col < W; col++)
for (int row = H - 1; row >= 0; row--) {
if (map[row][col] == 0) {
for (int tmp = row - 1; tmp >= 0; tmp--) {
if (map[tmp][col] != 0) {
map[row][col] = map[tmp][col];
map[tmp][col] = 0;
break;
}
}
}
}
- 다음 게임으로 넘어가기
// 다시 dfs
for (int i = 0; i < W; i++) {
dfs(i, depth + 1);
}
// 배열 원상복구
for (int i = 0; i < H; i++)
map[i] = copy[i].clone();
다음 게임으로 넘어가기 위해 dfs함수를 호출한다.
그리고 static으로 선언된 배열을 다시 원래대로 복원해야 한다.
전체 코드
package 모의sw;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class SWEA_5656_벽돌깨기 {
static int N, W, H;
static int[][] map;
static int[] dr = { 1, -1, 0, 0 };
static int[] dc = { 0, 0, 1, -1 };
static int ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken()); // col
H = Integer.parseInt(st.nextToken()); // row
ans = Integer.MAX_VALUE;
map = new int[H][W];
for (int i = 0; i < H; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < W; j++)
map[i][j] = Integer.parseInt(st.nextToken());
}
// col에 따라 벽돌깨기 진행
for (int i = 0; i < W; i++)
dfs(i, 0);
if (ans == Integer.MAX_VALUE)
ans = 0;
System.out.println("#" + t + " " + ans);
}
}
static void dfs(int i, int depth) {
if (depth == N) {
int cnt = 0;
for (int r = 0; r < H; r++)
for (int c = 0; c < W; c++)
if (map[r][c] != 0)
cnt++;
ans = Math.min(ans, cnt);
return;
}
for (int r = 0; r < H; r++)
if (map[r][i] != 0) {
game(r, i, depth);
break;
}
}
static void game(int r, int c, int depth) {
// bfs
Queue<int[]> q = new LinkedList<>();
q.add(new int[] { r, c, map[r][c] });
int[][] copy = new int[H][W];
for (int i = 0; i < H; i++)
copy[i] = map[i].clone(); // 원래 배열 저장
while (!q.isEmpty()) {
int[] tmp = q.poll();
int tmpr = tmp[0];
int tmpc = tmp[1];
int val = tmp[2];
map[tmpr][tmpc] = 0;
label: for (int d = 0; d < 4; d++)
for (int v = 1; v < val; v++) {
int nr = tmpr + dr[d] * v;
int nc = tmpc + dc[d] * v;
if (nr < 0 || nr >= H || nc < 0 || nc >= W)
continue label;
if (map[nr][nc] > 0) { // 1인 경우는 주변에 영향x
q.add(new int[] { nr, nc, map[nr][nc] });
map[nr][nc] = 0;
}
}
}
// 0이 있으면 아래로 당기기
for (int col = 0; col < W; col++)
for (int row = H - 1; row >= 0; row--) {
if (map[row][col] == 0) {
for (int tmp = row - 1; tmp >= 0; tmp--) {
if (map[tmp][col] != 0) {
map[row][col] = map[tmp][col];
map[tmp][col] = 0;
break;
}
}
}
}
// 다시 dfs
for (int i = 0; i < W; i++) {
dfs(i, depth + 1);
}
// 배열 원상복구
for (int i = 0; i < H; i++)
map[i] = copy[i].clone();
}
}
728x90
'문제 풀이 > SWEA' 카테고리의 다른 글
[SWEA][모의 SW 테스트] 2105 - 디저트 카페 (자바/Java) (0) | 2022.09.27 |
---|---|
[SWEA] 1767 - 프로세서 연결하기 (자바/Java) (1) | 2022.09.23 |
[SWEA] 4008 - 숫자 만들기 (자바/Java) (0) | 2022.09.22 |
[SWEA] 2819 - 격자판의 숫자 이어 붙이기 (0) | 2022.08.25 |
[SWEA] 1231 - 중위 순회 (0) | 2022.08.23 |