Life Engineering
[SWEA 5656] 벽돌 깨기 (Java) 본문
https://swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AWXRQm6qfL0DFAUo
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution_SWEA_5656 {
static int[] dr= {-1,1,0,0};
static int[] dc= {0,0,-1,1};
static int T, N, W, H;
static int[][] map;
static int answer;
static int shoot;
static int start_r, start_c;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=null;
T=Integer.parseInt(br.readLine());
for (int t=1; t<=T; t++) {
answer=Integer.MAX_VALUE; //남은 벽돌 갯수
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];
int total=0;
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());
if (map[i][j]!=0) total++;
}
}
dfs(0, total, map);
System.out.println("#"+t+" "+answer);
}
}
private static void dfs(int cnt, int sum, int[][] copyMap) { //sum: 남은 갯수 (남은거 최소화)
if (cnt==N || sum==0) {
answer=Math.min(answer, sum);
return;
}
for (int i=0; i<W; i++) {
if (isPossible(i, copyMap)) {
shoot=0;
int[][] tempMap=hit(i, copyMap);
tempMap=move(tempMap);
dfs(cnt+1, sum-shoot, tempMap);
}
}
}
private static int[][] move(int[][] tempMap) {
int[][] newMap=new int[H][W];
for (int i=0; i<W; i++) {
int cnt=H-1;
for (int j=H-1; j>=0; j--) {
if (tempMap[j][i]!=0) {
newMap[cnt--][i]=tempMap[j][i];
}
}
}
return newMap;
}
private static int[][] hit(int col, int[][] copyMap) {
int[][] tempMap=new int[H][W];
for (int i=0; i<H; i++) {
tempMap[i]=Arrays.copyOf(copyMap[i], W);
}
Queue<int[]> q=new LinkedList<>();
q.add(new int[] {start_r, start_c, tempMap[start_r][start_c]});
tempMap[start_r][start_c]=0;
shoot++;
while (!q.isEmpty()) {
int[] curr=q.poll();
int r=curr[0];
int c=curr[1];
int range=curr[2]-1;
for (int i=0; i<4; i++) {
for (int j=1; j<=range; j++) {
int nr=r+(dr[i]*j);
int nc=c+(dc[i]*j);
if (nr<0 || nc<0 || nr>=H || nc>=W) continue;
if (tempMap[nr][nc]!=0) {
int nrange=tempMap[nr][nc];
tempMap[nr][nc]=0;
shoot++;
q.add(new int[] {nr, nc, nrange});
}
}
}
}
return tempMap;
}
private static boolean isPossible(int col, int[][] copyMap) {
for (int i=0; i<H; i++) {
if (copyMap[i][col]!=0) {
start_r=i;
start_c=col;
return true;
}
}
return false;
}
}
BFS+구현+시뮬레이션 문제
다 짜놓고 answer, sum을 헷갈려서 헤맸고.. 또 괜히 가지치기 한다고 하는 바람에 또 헤맸다..
if (sum>answer) 이면 가지치기 해주는 걸로 처음에 짰는데, 이러면 안된다. sum이 지금 answer보다 크다고 하더라도 나중에 더 answer보다 줄어들 가능성이 있기 때문에 가지치기 해주면 안된다! 기계적으로 코드짜지 말것..
벽돌이 깨지는 과정은 BFS 로 구현했다. 큐에 차례대로 깨진 대상을 넣어주면서 주변 4방향*range 만큼 탐색하게 했다.
또한 여기서 주의할 점이, N번을 다 던지지 않더라도 벽돌이 모두 깨진 경우가 존재하는데, sum==0 일때 답안을 갱신하고 함수를 return 하게 해주어 그 경우도 구현해준다.
hit: 벽돌 깨지는 함수
move: 깨지면 자리 이동시켜주는 함수
아래 코드는 sum==0일때 더이상 탐색할 필요 없으므로 return 값을 이용해 탐색을 끝내도록 한 코드.
sum==0 이면 return true를 하고, 만약 dfs 호출 결과가 true라면 계속 true를 리턴하게 함으로써 재귀를 종료시켜버린다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution_SWEA_5656 {
static int[] dr= {-1,1,0,0};
static int[] dc= {0,0,-1,1};
static int T, N, W, H;
static int[][] map;
static int answer;
static int shoot;
static int start_r, start_c;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=null;
T=Integer.parseInt(br.readLine());
for (int t=1; t<=T; t++) {
answer=Integer.MAX_VALUE; //남은 벽돌 갯수
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];
int total=0;
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());
if (map[i][j]!=0) total++;
}
}
dfs(0, total, map);
System.out.println("#"+t+" "+answer);
}
}
private static boolean dfs(int cnt, int sum, int[][] copyMap) { //sum: 남은 갯수 (남은거 최소화)
if (sum==0) {
answer=0;
return true;
}
if (cnt==N) {
answer=Math.min(answer, sum);
return false;
}
for (int i=0; i<W; i++) {
if (isPossible(i, copyMap)) {
shoot=0;
int[][] tempMap=hit(i, copyMap);
tempMap=move(tempMap);
if (dfs(cnt+1, sum-shoot, tempMap)) return true;
}
}
return false;
}
private static int[][] move(int[][] tempMap) {
int[][] newMap=new int[H][W];
for (int i=0; i<W; i++) {
int cnt=H-1;
for (int j=H-1; j>=0; j--) {
if (tempMap[j][i]!=0) {
newMap[cnt--][i]=tempMap[j][i];
}
}
}
return newMap;
}
private static int[][] hit(int col, int[][] copyMap) {
int[][] tempMap=new int[H][W];
for (int i=0; i<H; i++) {
tempMap[i]=Arrays.copyOf(copyMap[i], W);
}
Queue<int[]> q=new LinkedList<>();
q.add(new int[] {start_r, start_c, tempMap[start_r][start_c]});
tempMap[start_r][start_c]=0;
shoot++;
while (!q.isEmpty()) {
int[] curr=q.poll();
int r=curr[0];
int c=curr[1];
int range=curr[2]-1;
for (int i=0; i<4; i++) {
for (int j=1; j<=range; j++) {
int nr=r+(dr[i]*j);
int nc=c+(dc[i]*j);
if (nr<0 || nc<0 || nr>=H || nc>=W) continue;
if (tempMap[nr][nc]!=0) {
int nrange=tempMap[nr][nc];
tempMap[nr][nc]=0;
shoot++;
q.add(new int[] {nr, nc, nrange});
}
}
}
}
return tempMap;
}
private static boolean isPossible(int col, int[][] copyMap) {
for (int i=0; i<H; i++) {
if (copyMap[i][col]!=0) {
start_r=i;
start_c=col;
return true;
}
}
return false;
}
}
'Problem Solving' 카테고리의 다른 글
[BOJ 10159] 저울 (Java) (0) | 2022.04.05 |
---|---|
[JUNGOL 2577] 회전 초밥(고) (0) | 2022.04.05 |
[BOJ 1644] 소수의 연속합 (Java) (0) | 2022.04.04 |
[SWEA 1767] 프로세서 연결하기 (Java) (0) | 2022.04.04 |
[BOJ 1175] 배달 (Java) (0) | 2022.04.04 |