[SWEA 5656] 벽돌 깨기 (Java)

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

SW Expert Academy

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