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

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

SW Expert Academy

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Solution {
	public static int T, N, W, H, ans = 0;
	public static int[] arr;
	public static int[][] map, copyMap;
	public static int[] dr = { -1, 0, 1, 0 };
	public static int[] dc = { 0, 1, 0, -1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());

			map = new int[H][W];
			copyMap = new int[H][W];
			arr = new int[N];

			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());
				}
			}

			ans = W * H;

			dfs(0);

			System.out.println("#" + tc + " " + ans);
		}

	}

	public static void dfs(int depth) {
		if (depth == N) {
			copy();
			// 벽돌 부수기
			for (int d : arr) {
				busu(d);
			}

			// 남은 벽돌 계산
			int cnt = 0;
			for (int i = 0; i < H; i++) {
				for (int j = 0; j < W; j++) {
					if (copyMap[i][j] > 0) {
						cnt++;
					}
				}
			}

			if (cnt < ans) {
				ans = cnt;
			}

			return;
		}
		for (int i = 0; i < W; i++) {
			arr[depth] = i;
			dfs(depth + 1);
		}
	}

	public static void busu(int at) {
		int r = 0;
		int c = at;
		Queue<int[]> q = new LinkedList<>();
		while (r <= H-1) {
			if (copyMap[r][c] == 0) {
				r += 1;
			} else {
				q.offer(new int[] { r, c, copyMap[r][c] });
				copyMap[r][c] = 0;
				break;
			}
		}

		while (!q.isEmpty()) {
			int[] cur = q.poll();

			if (cur[2] == 1) {
				copyMap[cur[0]][cur[1]] = 0;
				continue;
			}

			int size = cur[2];
			for (int i = 1; i < size; i++) {
				for (int d = 0; d < 4; d++) {
					int nr = cur[0] + dr[d] * i;
					int nc = cur[1] + dc[d] * i;
					if (nr < 0 || nr >= H || nc < 0 || nc >= W)
						continue;
					if (copyMap[nr][nc] != 0) {
						q.offer(new int[] { nr, nc, copyMap[nr][nc] });
						copyMap[nr][nc] = 0;
					}
				}
			}
		}

		down();

		
	}

	public static void down() {
		
		for(int i =0;i<W;i++) {
			Stack<Integer> st = new Stack<>();
			for(int j =0;j<H;j++) {
				if(copyMap[j][i] > 0) {
					st.add(copyMap[j][i]);
					copyMap[j][i] = 0;
				}
			}
			int ct = H-1;
			while(!st.isEmpty()) {
				int cur = st.pop();
				copyMap[ct][i] = cur;
				ct--;
			}
		}
	}

	public static void copy() {
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				copyMap[i][j] = map[i][j];
			}
		}
	}
}

 

 

## 풀이 사항
풀이 일자: 2024.09.09
풀이 시간: 120분
채점 결과: 정답
예상 문제 유형: 구현

## 풀이 방법
1. 역시 중복순열로 공을 떨어뜨릴 위치를 미리 배열로 정해주었다.
2. 다 정했다면 맵을 복사해주고 벽돌을 깨고 남은 벽돌을 계산한 뒤 정답을 갱신해 주었다.
3. 벽돌을 깨는건 bfs 방식으로 가장 위랑 가까운 벽돌부터 큐에 넣어주고 좌표에 함께 벽돌의 사이즈를 넣어 그만큼 사방으로 터질 수 있게 하였다.
4. 벽돌을 다 부쉈다면 스택을 이용해서 아래로 벽돌을 내려준다.
5. 처음에 넣는 벽돌도 0으로 만들어야 하는데 디버그 중에 발견, 방문배열을 사용했다가 더 큰 사이즈의 벽돌을 만났을때 초과하는 경우를 생각못해서 방문배열을 없애고 전부 탐색해주었다.

 

옆그레이드 코드 !

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Solution {
	public static int T, N, W, H, ans = 0;
	public static int[][] map;
	public static int[] dr = { -1, 0, 1, 0 };
	public static int[] dc = { 0, 1, 0, -1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());

			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());
				}
			}

			ans = W * H;

			dfs(0, map);

			System.out.println("#" + tc + " " + ans);
		}

	}

	public static void dfs(int depth, int[][] curMap) {
		if (depth == N) {
			int cnt = chk(curMap);
			
			if (cnt < ans) {
				ans = cnt;
			}

			return;
		}
		
		for (int i = 0; i < W; i++) {
			int[][] nMap = copy(curMap);
			nMap = busu(i, nMap);
			dfs(depth + 1, nMap);
		}
	}

	private static int chk(int[][] curMap) {
		int cnt = 0;
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				if (curMap[i][j] > 0) {
					cnt++;
				}
			}
		}
		
		return cnt;
	}

	private static int[][] copy(int[][] curMap) {
		int[][] nMap = new int[H][W];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
            	nMap[i][j] = curMap[i][j];
            }
        }
        return nMap;
	}

	public static int[][] busu(int at, int[][] map) {
		int r = 0;
		int c = at;
		Queue<int[]> q = new LinkedList<>();
		while (r <= H-1) {
			if (map[r][c] == 0) {
				r += 1;
			} else {
				q.offer(new int[] { r, c, map[r][c] });
				map[r][c] = 0;
				break;
			}
		}

		while (!q.isEmpty()) {
			int[] cur = q.poll();

			if (cur[2] == 1) {
				map[cur[0]][cur[1]] = 0;
				continue;
			}

			int size = cur[2];
			for (int i = 1; i < size; i++) {
				for (int d = 0; d < 4; d++) {
					int nr = cur[0] + dr[d] * i;
					int nc = cur[1] + dc[d] * i;
					if (nr < 0 || nr >= H || nc < 0 || nc >= W)
						continue;
					if (map[nr][nc] != 0) {
						q.offer(new int[] { nr, nc, map[nr][nc] });
						map[nr][nc] = 0;
					}
				}
			}
		}

		map = down(map);

		return map;
	}

	public static int[][] down(int[][] map) {
		for(int i =0;i<W;i++) {
			Stack<Integer> st = new Stack<>();
			for(int j =0;j<H;j++) {
				if(map[j][i] > 0) {
					st.add(map[j][i]);
					map[j][i] = 0;
				}
			}
			int ct = H-1;
			while(!st.isEmpty()) {
				int cur = st.pop();
				map[ct][i] = cur;
				ct--;
			}
		}
		
		return map;
	}
}

 

중복순열을 구해서 한번에 벽돌깨는것을 Map값을 파라미터로 넘겨주어, 깨면서 결과로 나온 nMap으로 다시 재귀를 들어갔다.

 

시간초가 약 3배정도 빨라졌다.