- [모의 SW 역량테스트] 벽돌 깨기
N번 반복 => 1~W번 모두 선택가능 & 순서있음 => 중복순열 => DFS
벽돌 삭제하기 => 처음벽돌~영향받은벽돌~이어서영향받은벽돌.... => BFS로 순차적으로 삭제
중간에 공간이 비기 때문에 벽돌 내려주기 => 인덱스 사용
벽돌 내리기 로직
i(벽돌인지 빈칸인지 확인) 와 row(빈칸위치를 안내) 를 사용해서 벽돌을 내린다.
- i가 벽돌을 가리킴 & i=r이면 현위치까지 벽돌로 꽉차있다는 의미 => row와 i를 1만큼 각각 감소
- i가 벽돌 가리킴 & i != r 이라면 i위치 벽돌을 row위치로 바꿔준다 => row는 빈칸을 가리켜야 하므로 -1하여 위로 한칸 올라감 & i도 한칸 올라감
clone과 temp를 왜 따로 만들어야 하나요??
temp는 현재 보드상태입니다. for문을 돌면서 i번째 열선택과 j번째 열선택은 temp상태에서 변화되어야 합니다. clone을 해놓지 않고 실행하면 temp상태가 아닌 이전 열에서 벽돌제거된 상태에서 시작되기 때문에 정확한 답이 나오지 않습니다!
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution {
private static int[][] board;
private static int N,H,W;
private static int answer;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
answer = W*H; //남는 블럭 수
board = new int[H][W]; //블럭 입력 상태
int[] topList = new int[W+1]; //맨위에 행번호 입력 리스트 & 마지막값:총블럭수
Arrays.fill(topList, -1);
for (int i = 0; i < H; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < W; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
if(board[i][j]!=0) {
topList[W]++; //블럭수+1
if(topList[j]==-1) { //맨위에 행번호 세팅
topList[j]=i;
}
}
}
}
dfs(0, board, topList); //수행횟수, 현보드상태, 맨위값리스트
sb.append("#").append(t).append(" ").append(answer).append("\n");
}
sb.setLength(sb.length()-1);
System.out.println(sb);
}
private static int[][] clone;
private static void dfs(int number, int[][] temp, int[] topList) {
// topList에서 하나씩 선택
// 선택값에 따라 없어질 값들 queue에 넣기
// queue에 있는 값들 따라 없어질값들 넣기(0으로 만들기, queue에 r,c,val 넣기)
// 남은 벽돌 밑으로 내리기
if(number==N || topList[W]==0) {
answer = Math.min(answer, topList[W]);
return;
}
for (int i = 0; i < W; i++) { // topList에서 하나씩 선택
int loc = topList[i]; //i번째 열에서 제일 첫번째 행번호
if(loc>=H || loc<0) continue; //H이상 0미만이면 패스
clone = new int[H][W];
for (int j = 0; j < H; j++) { //temp 복사
for (int k = 0; k < W; k++) {
clone[j][k] = temp[j][k];
}
}
int[] tempTopList = goBreak(i,loc); // col,row값으로 벽돌없애기
dfs(number+1, clone, tempTopList);
}
}
private static int[] dx = {0,1,0,-1};
private static int[] dy = {1,0,-1,0};
private static int[] goBreak(int col, int row) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {row,col,clone[row][col]}); //현위치, 없앨수있는범위
clone[row][col] = 0;
while(!queue.isEmpty()) {
int[] pick = queue.poll();
for (int dir = 0; dir <4; dir++) { //방향
int t =0;
while(++t<pick[2]) { //가능한 범위까지 queue에 넣기
int nr = pick[0]+t*dx[dir];
int nc = pick[1]+t*dy[dir];
if(nr<0 || nr>=H || nc<0 || nc>=W) break;
if(clone[nr][nc]>0) {
if(clone[nr][nc]>1)
queue.add(new int[] {nr,nc,clone[nr][nc]});
clone[nr][nc] = 0;
}
}
}
}
return goArrange(); //남은 벽돌 밑으로 내리기
}
private static int[] goArrange() {
int[] tempTopList = new int[W+1];
int count = 0;
for (int j = 0; j < W; j++) {
int row = H-1;
for (int i = H-1; i >=0; i--) {
if(clone[i][j]!=0) {
count++;
if(row!=i) {
clone[row][j] = clone[i][j];
clone[i][j] = 0;
}
row--;
}
}
tempTopList[j] = row+1;
}
tempTopList[W] = count;
return tempTopList;
}
}좀 더 효율적/가독성 높은 코드
- 이미 최소 답인 0이 나오면 그 뒤에 과정필요x => 중단 true/false 처리 추가
- clone 복사하는 일은 따로 copy함수로 빼자!
- clone한 객체를 전역변수로 빼지 않아도 사용가능 => 객체는 주소값을 넘기기 때문!
- 벽돌내리는 함수에서 인덱스 사용하지 않고 리스트 사용해서도 구현가능!
벽돌 내리기 로직
우선 j열에 있는 벽돌을 밑에서부터 순서대로 list에 채운다
이후에 list에 있는 벽돌을 순차적으로 밑에서부터 채워준다
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution {
static class Point {
int r,c,cnt;
public Point(int r, int c, int cnt) {
super();
this.r = r;
this.c = c;
this.cnt = cnt;
}
}
private static int N,H,W,min;
private static int[] dx = {0,1,0,-1};
private static int[] dy = {1,0,-1,0};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
int[][] 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());
}
}
min = Integer.MAX_VALUE;
go(0,map);
sb.append("#").append(t).append(" ").append(min).append("\n");
}
sb.setLength(sb.length()-1);
System.out.println(sb);
}
// 중복순열로 구슬 떨어뜨리기
private static boolean go(int cnt, int[][] map) { //cnt : 구슬 떨어뜨린 횟수
int result = getRemain(map);
if(result ==0) { //모두 빈칸(깨뜨릴 벽돌이 없다!)
min = 0;
return true;
}
if(cnt==N) {
min = Math.min(min, result);
return false;
}
int[][] newMap = new int[H][W];
//매 열마다 구슬 떨어뜨리는 시도
for (int c = 0; c < W; c++) {
//해당열에 구슬을 떨어뜨려 맞는 벽돌 찾기
int r=0;
while(r<H && map[r][c]==0) ++r;
if(r==H) { //맞는 벽돌이 없음(모두 빈칸)
continue; //다음 열로 구슬 떨어뜨리기
}else {
//기존 cnt-1구슬까지의 상태로 초기화
copy(map, newMap);
//벽돌 깨뜨리기
boom(newMap,r,c);
//벽돌 내리기 (꺠지고 난 빈 공간 처리)
down(newMap);
//다음 구슬 던지기
if(go(cnt+1,newMap)) return true;
}
}
return false;
}
private static int getRemain(int[][] map) {
int count = 0;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if(map[i][j]>0) ++count;
}
}
return count;
}
private static void down(int[][] map) {
for (int c = 0; c < W; c++) {
int r = H-1;
for (;r>=0;r--) {
if(map[r][c]>0) { //벽돌이면
list.add(map[r][c]);
map[r][c] = 0;
}
}//벽돌 리스트에 넣기
r = H;
for (int b : list) { // 리스트에 담긴 벽돌 차례대로 꺼내여 맨 아래행부터 채우기
map[--r][c] = b;
}
list.clear();
}
}
private static void boom(int[][] map, int r, int c) {
Queue<Point> queue = new LinkedList<Point>();
if(map[r][c]>1) {
queue.offer(new Point(r,c,map[r][c]));
}
map[r][c] = 0; //제거처리(방문처리 효과)
while(!queue.isEmpty()) {
Point p = queue.poll();
for (int d = 0; d < 4; d++) {
int nr = p.r;
int nc = p.c;
for (int k = 1; k < p.cnt; k++) {
nr += dx[d];
nc += dy[d];
if(nr>=0 && nr<H && nc>=0 && nc<W && map[nr][nc]!=0) {
if(map[nr][nc]>1) {
queue.offer(new Point(nr,nc,map[nr][nc]));
}
map[nr][nc]=0;
}
}
}
}
}
private static void copy(int[][] map, int[][] newMap) {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
newMap[i][j] = map[i][j];
}
}
}
}
에국은 에구구구...