개요
여러번 풀어도 구현이 빡쎈 문제
이런느낌의 문제는 이런식으로 구현하고, 여기에서 탐색을 이렇게 활용하면 되겠구나를 느낀 문제였다.
문제분석
이렇게 생긴 곳에 공을 아무 위치에나 던졌을때, 공은 일직선으로 부딪히는 곳에 가서 터진다.
그 터지는 범위는 공에 적인 숫자 - 1의 범위로 터지게 되며,해당 공의 범위에 해당하는 벽돌 또한 연쇄적으로 폭발한다.
여기에서 우리는 블록이 가장 적게 남을때 블록의 개수를 찾아야 한다.
여기서 우리는 구현부를 세개로 나눌 수 있다.
1.구슬을 어느 위치에서 던질지
2.구슬이 터지는 연쇄작용
3.구슬이 다 터진 뒤 블록이 내려오는 것
첫번째의 경우 단순하게 dfs를 이용하여 중복순열을 구하는 코드를 작성해주면 되기 때문에 순조롭게 진행되었다.
두번째 부터 고난이 시작된다. 구슬이 터지는 연쇄작용을 어떻게 구현하지?라는 생각이 들었다.
처음에는 단순하게 구슬이 맞은 부분만 for문을 돌려서 4방향으로만 터지는 코드를 작성했지만. 해당 코드는 연쇄적으로 터지는 블록에 대한 고려를 하지 않았다.
이러한 상황에서 어떠한 방식으로 구현해야할까 고민하던 중 BFS를 통해서 터질 수 있는 부분을 전체 탐색하여 지워주게 되면 해당 문제가 해결될 것 이라고 생각하게 되었다.
알고리즘은 다음과 같다.
터지는 위치를 넘겨준다. 블록의 정보를 저장하는 큐를 하나 만든다음 (블록의 파워도 저장한다!)
로직이 시작되는 순간 블록은 이미 터진것이나 마찬가지 이기 때문에, 블록의 파워 값을 0으로 바꾸어준다.
이제부터 반복작업의 시작이다.
BFS로 탐색하며, POWER 범위에 해당하는 모든 블럭들을 큐에 담아가면서 연쇄적으로 블록이 터지는 작업을 구현해주면 된다.
물론 공 하나에 공이 가지고 있는 파워만큼 반복작업을 해야한다 파워만큼 좌표의 값이 늘어나기 때문에 해당 부분은 FOR문을 통해서 늘려준다.
해당 작업을 마치게 되면,벽돌이 터지는 연쇄 작업이 마무리 된다.
해당 작업을 마치고,0이 된 벽돌이 내려앉아야 하는 작업을 한다. 해당작업을 통해 빈공간을 매꾸어 준다.
블록이 떨어진다 즉, 빈공간이 없이 아래로 차곡차곡 쌓여서 모여야 한다.
여기에서 생각나는 자료구조가 하나 있다. 바로 스택이다.
각각의 블록기둥 하나하나마다 데이터를 스택에 쌓아준다. 단, 여기에 0은 들어가지 않도록 차곡차곡 쌓아준다. 여기서 헷갈리지 말아야 할 것은, 가장 위에 있는 블록의 인덱스가 0이라는 것이다.
즉,가장 위에있는 블록부터 차근차근 스택에 쌓아준다. 0이 없이 쌓인 블록은 아래부터 다시 쌓아주어야 한다 (중간에 0이 빠지도록 쌓아놓았으니 이를 POP 하면 원상복구가 된다)
이를 코드로 확인해보자
문제풀이
최적화 전
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
* @author onyoo
* @performance
* @category
* @note
* 구슬은 좌우로만 이동가능하고 맨위에 있는 벽돌만 깨트릴 수 있음
* 구슬이 명중한 벽돌은 상하좌우로 벽돌에 적힌 수 - 1 만큼 같이 제거 됨
* @see
* https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo
* @since 2023/11/05
**/
public class Solution {
static class Point{
int x,y,power;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public Point(int x, int y, int power) {
this.x = x;
this.y = y;
this.power = power;
}
}
static int T,W,H,N;
// W * H
// 구슬 쏘는 횟수 N
static int[][] map;
static int[][] copy;
static Point[] dir = {new Point(0,1),new Point(0,-1),new Point(1,0),new Point(-1,0)};
static int min;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for(int t=1;t<T+1;t++){
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];
copy = 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());
copy[i][j] = map[i][j];
}
}
min = Integer.MAX_VALUE;
dfs(0,new int[N]);
System.out.printf("#%d %d\n",t,min);
}
}
static void dfs(int depth,int[] selected){
//중복순열
//구슬을 어떤 위치에서 쏴도 상관없다
//구슬을 쏘는 위치가 중복되어도 상관없다
if(depth == N){
//구슬을 쏘자
start(selected);
min = Math.min(countMap(),min); // 최솟값을 갱신한다
copyMap();
// 미리 저장된 COPY본으로 되돌려놓는다
// 구슬을 터트리고 난리를 쳐놓았으니 청소를 해놔야 한다
return;
}
for(int w=0;w<W;w++){
selected[depth] = w; // 중복조합
dfs(depth+1,selected);
}
}
static void start(int[] arr){
//구슬을 하나씩 쏜다
int x = 0;
int y = 0;
for(int i=0;i<N;i++){
for(int j=0;j<H;j++){
if(map[j][arr[i]] != 0){
// 구슬이 처음으로 마주치는 블록을 찾는다
x = j;
y = arr[i];
break;
}
}
bfs(x,y);
// 처음으로 마주치는 블록부터 시작하여 연쇄작업을 시작한다
blockdown();
//블록이 내려앉는 작업을 한다
}
}
static void bfs(int x,int y){
Queue<Point> que = new ArrayDeque<>();
que.add(new Point(x,y,map[x][y])); // 공의 파워를 기억함
map[x][y] = 0;// 공이 부숴졌기 때문에 공의 파워를 초기화해줌
while(!que.isEmpty()){
Point curr = que.poll();
int power = curr.power;
for(int i=1;i<power;i++){
// 파워만큼 반복
for(Point d : dir){
int nx = curr.x + d.x * i;
int ny = curr.y + d.y * i;
if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
if(map[nx][ny] == 0) continue;
que.add(new Point(nx,ny,map[nx][ny]));
map[nx][ny] = 0; // 터진 블록은 파워가 0이 된다
}
}
}
}
static void blockdown(){
Stack<Integer> stack = new Stack<>();
for(int i=0;i<W;i++){
for(int j=0;j<H;j++){
if(map[j][i] != 0) stack.add(map[j][i]);
}
//j=0인 곳이 TOP 위치임을 명심하자
for(int j=H-1;j>=0;j--){
if(stack.isEmpty()) map[j][i] = 0;
else map[j][i] = stack.pop();
}
//맨 아랫값부터 차곡차곡 쌓아준다
}
}
static int countMap(){
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;
}
static void copyMap(){
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
map[i][j] = copy[i][j];
}
}
}
}
최적화 후 (1)
위의 코드는 남은 블록의 개수가 0이 되었는데도 동작하게 되어 시간이 오래걸리는 부분이 있다.
이 부분을 최적화 한 코드를 아래에 첨부한다 ! 간단하게 최적화 할 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
/**
* @author onyoo
* @performance
* @category
* @note
* @see
* @since 11/29/23
**/
public class 벽돌다시깨기 {
static class Point{
int h,w;
int value;
public Point(int h, int w, int value) {
this.h = h;
this.w = w;
this.value = value;
}
}
static int T,N,W,H;
static int[][] map,copy;
static int answer; // 최솟값을 저장함
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for(int t=1;t<T+1;t++){
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];
copy = new int[H][W];
answer = Integer.MAX_VALUE;
for(int h=0;h<H;h++){
st = new StringTokenizer(br.readLine()," ");
for(int w=0;w<W;w++){
map[h][w] = Integer.parseInt(st.nextToken());
copy[h][w] = map[h][w]; // 이후 원본으로 되돌려줄 카피본
}
}
dfs(0,new int[N]);
sb.append("#").append(t).append(" ").append(answer).append("\n");
}
System.out.println(sb);
}
static void dfs(int depth,int[] selected){
if(depth == N){
// 던지는 위치를 모두 다 정했다면
for(int j: selected){
for(int i=0;i<H;i++){
if(map[i][j] == 0) continue;
crush(new Point(i,j,map[i][j]));
break;
}
//빈공간을 내려주기
down();
if(count() == 0) {
answer = 0;
return;
}
}
answer = Math.min(answer,count());
copyMap();
return;
}
for(int i=0;i<W;i++){
selected[depth] = i;
dfs(depth+1,selected);
}
//중복이 나와도 상관없음
//순서가 중요하기 때문에 중복순열
}
static void crush(Point p){
Queue<Point> que = new ArrayDeque<>();
que.add(p);
map[p.h][p.w] = 0; // 터트렸기 때문에 초기화
while(!que.isEmpty()){
Point curr = que.poll();
int size = curr.value;
//터지는 강도
for(int s=1;s<size;s++){
for(int i=0;i<4;i++){
int nx = curr.h + dx[i] * s;
int ny = curr.w + dy[i] * s;
if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
//유효하지 않은 좌표면 가지 않음
if(map[nx][ny] == 0) continue;
que.add(new Point(nx,ny,map[nx][ny]));
map[nx][ny] = 0; // 큐에 넣은 자리는 0으로 바꿔준다
}
}
}
}
static void down(){
//빈 공간을 내려주기
for(int j=0;j<W;j++){
Stack<Integer> stack = new Stack<>();
for(int i=0;i<H;i++){
if(map[i][j] == 0) continue;
stack.add(map[i][j]);
}
for(int i=H-1;i>=0;i--){
if(stack.isEmpty()){
map[i][j] = 0;
continue;
}
map[i][j] = stack.pop();
}
}
}
static int count(){
int cnt = 0;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(map[i][j] > 0 ) cnt++;
}
}
return cnt;
}
static void copyMap(){
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
map[i][j] = copy[i][j];
}
}
}
}
최적화 후 (2)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class 벽돌깨기 {
static class Point{
int x,y;
int range;
public Point(int x, int y, int range) {
this.x = x;
this.y = y;
this.range = range;
}
}
static int T,N,W,H;
static int answer;
static int[][] map,copy;
static int[] dx = {0,0,-1,1};
static int[] dy = {-1,1,0,0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for(int t=1;t<T+1;t++){
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];
copy = new int[H][W];
answer = Integer.MAX_VALUE;
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());
copy[i][j] = map[i][j];
}
}
dfs(0,new int[N]);
sb.append("#").append(t).append(" ").append(answer).append("\n");
}
System.out.println(sb);
}
static void dfs(int depth,int[] selected){
if(depth == N){
if(answer == 0) return;
//N개의 숫자를 골라야 한다
for(int j : selected){
for(int i=0;i<H;i++){
if(map[i][j] == 0) continue;
// 벽돌을 터트린다
boom(new Point(i,j,map[i][j]));
break;
}
if(count() == 0) {
answer = 0;
return;
} // 남은 벽돌의 개수를 세어보았을때, 이미 0개라면 더이상 진행하지 않는다.
down();
}
answer = Math.min(answer,count());
copyMap();
return;
}
for(int i=0;i<W;i++){
selected[depth] = i;
dfs(depth+1,selected);
}
}
static void boom(Point start){
Queue<Point> que = new ArrayDeque<>();
que.add(start);
map[start.x][start.y] = 0; // 터졌다는 표시를 해줍니다
while(!que.isEmpty()){
Point curr = que.poll();
int range = curr.range;
for(int r=1;r<range;r++){
// 범위는 1부터 시작해서 range-1까지 터진다
for(int i=0;i<4;i++){
int nx = curr.x + dx[i] * r;
int ny = curr.y + dy[i] * r;
if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
if(map[nx][ny] == 0) continue; // 빈공간이면 터지지 않는다
que.add(new Point(nx,ny,map[nx][ny]));
map[nx][ny] = 0; // 큐에 들어갔으니 폭발할것이기 때문에, 0으로 변경
}
}
}
}
static int count(){
int cnt = 0;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(map[i][j] > 0) cnt++;
}
}
return cnt;
}
static void down(){
for(int j=0;j<W;j++){
Stack<Integer> stack = new Stack<>();
for(int i=0;i<H;i++){
if(map[i][j] == 0) continue;
stack.add(map[i][j]);
}
for(int i=H-1;i>=0;i--){
if(stack.isEmpty()) {
map[i][j] = 0;
continue;
}
map[i][j] = stack.pop();
}
}
}
static void copyMap(){
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
map[i][j] = copy[i][j];
}
}
}
}
반갑습니다 ! 백엔드 개발 공부를 하고있습니다.