[SWEA]5656 벽돌깨기.java
1.문제
2.코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
static int N,W,H;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int tc=1; tc<=T; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
result = 987654321;
int[][] brick = new int[H][W];
for(int i=0; i<H; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<W; j++) {
brick[i][j] = Integer.parseInt(st.nextToken());
}
}
bbreak(brick, 0);
if(result == 987654321) result = 0;
System.out.println("#"+tc+" "+result);
}
}
// static int time = 0;
static int result;
private static void bbreak(int[][] brick, int n) {
// System.out.println(++time);
// for(int[] line : brick) {
// for(int num : line) {
// System.out.print(num+" ");
// }
// System.out.println();
// }
// System.out.println();
if(n==N) {
int cnt = 0;
for(int i=0; i<H; i++) {
for(int j=0; j<W; j++) {
if(brick[i][j]!=0) {
cnt++;
}
}
}
result = Math.min(result, cnt);
return;
}
//첫번째부터 마지막 칸까지 한번씩 내려보기
for(int x=0; x<W; x++) {
for(int y=0; y<H; y++) {
if(brick[y][x]==0) continue;
//벽돌 부수기
int[][] tbrick = pop(brick,y,x);
//벽돌 내리기
tbrick = downing(tbrick);
//다음 회차
bbreak(tbrick, n+1);
break;
}
}
}
private static int[][] downing(int[][] tbrick) {
for(int y=H-2; y>=0; y--) {
for(int x=0; x<W; x++) {
if(tbrick[y][x]!=0 && tbrick[y+1][x]==0) {
int ty = y+1;
while(ty<H && tbrick[ty][x]==0) ty++;
tbrick[ty-1][x] = tbrick[y][x];
tbrick[y][x] = 0;
}
}
}
return tbrick;
}
private static int[][] pop(int[][] brick, int y, int x) {
if(brick[y][x]==0) return brick;
int[][] result = new int[H][W];
for(int i=0; i<H; i++) {
for(int j=0; j<W; j++) {
result[i][j] = brick[i][j];
}
}
int range = brick[y][x]-1;
result[y][x] = 0;
for(int i=1; i<=range; i++) {
if(y+i<H)
result = pop(result,y+i,x);
if(x+i<W)
result = pop(result,y,x+i);
if(y-i>=0)
result = pop(result,y-i,x);
if(x-i>=0)
result = pop(result,y,x-i);
}
return result;
}
}
3.Review
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
static int N,W,H;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int tc=1; tc<=T; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
result = 987654321;
int[][] brick = new int[H][W];
for(int i=0; i<H; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<W; j++) {
brick[i][j] = Integer.parseInt(st.nextToken());
}
}
bbreak(brick, 0);
if(result == 987654321) result = 0;
System.out.println("#"+tc+" "+result);
}
}
// static int time = 0;
static int result;
private static void bbreak(int[][] brick, int n) {
// System.out.println(++time);
// for(int[] line : brick) {
// for(int num : line) {
// System.out.print(num+" ");
// }
// System.out.println();
// }
// System.out.println();
if(n==N) {
int cnt = 0;
for(int i=0; i<H; i++) {
for(int j=0; j<W; j++) {
if(brick[i][j]!=0) {
cnt++;
}
}
}
result = Math.min(result, cnt);
return;
}
//첫번째부터 마지막 칸까지 한번씩 내려보기
for(int x=0; x<W; x++) {
for(int y=0; y<H; y++) {
if(brick[y][x]==0) continue;
//벽돌 부수기
int[][] tbrick = pop(brick,y,x);
//벽돌 내리기
tbrick = downing(tbrick);
//다음 회차
bbreak(tbrick, n+1);
break;
}
}
}
private static int[][] downing(int[][] tbrick) {
for(int y=H-2; y>=0; y--) {
for(int x=0; x<W; x++) {
if(tbrick[y][x]!=0 && tbrick[y+1][x]==0) {
int ty = y+1;
while(ty<H && tbrick[ty][x]==0) ty++;
tbrick[ty-1][x] = tbrick[y][x];
tbrick[y][x] = 0;
}
}
}
return tbrick;
}
private static int[][] pop(int[][] brick, int y, int x) {
if(brick[y][x]==0) return brick;
int[][] result = new int[H][W];
for(int i=0; i<H; i++) {
for(int j=0; j<W; j++) {
result[i][j] = brick[i][j];
}
}
int range = brick[y][x]-1;
result[y][x] = 0;
for(int i=1; i<=range; i++) {
if(y+i<H)
result = pop(result,y+i,x);
if(x+i<W)
result = pop(result,y,x+i);
if(y-i>=0)
result = pop(result,y-i,x);
if(x-i>=0)
result = pop(result,y,x-i);
}
return result;
}
}
구현 문제는 뭔가 해야하는거만 해야되서 편하다...
풀고나서 다른 사람들 코드를 구경했는데 속도는 느리지만 이렇게도 풀 수 있구나 느끼는게 많았다.
특히 정렬을 할때 스택을 써서 다시 채워준다던지...
Author And Source
이 문제에 관하여([SWEA]5656 벽돌깨기.java), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hakka_ame/SWEA5656-벽돌깨기.java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)