[코드트리/NOVICE MID] 십자 모양 폭발 (JAVA)

📖 문제

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• 시뮬레이션 - 2차원 격자 안에서의 폭발과 중력 적용하기

1) 범위 내의 폭탄을 터뜨린다. → 범위 확인 시, 맨해튼 거리 이용

2) 중력을 적용해 값이 0인 칸은 아래로 떨어트린다. → 새로운 2차원 배열을 생성해 각 열을 아래에서부터 위로 0이 아닌 값으로 채운다.

3) 완성된 임시배열의 결과를 원본배열에 적용한다.

 

 

💥 유의사항

맨해튼 거리 식

(|x1 - x2| + |y1 - y2|)

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int n, r, c, size;
    static int[][] grid;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        n = Integer.parseInt(br.readLine());
        grid = new int[n][n];
 
        for(int i = 0 ; i < n ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < n ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        st = new StringTokenizer(br.readLine(), " ");
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        r--; c--;
 
        size = grid[r][c];
 
        // 1) 폭탄 터뜨리기
        pop();
 
        // 2) 중력 적용하기 (아래에서 위로 올라오면서 채우기)
        int[][] tmp = new int[n][n];
        for(int col = 0 ; col < n ; col++) {
            int tmpRow = n - 1;
            for(int row = n - 1 ; row >= 0 ; row--) {
                if(grid[row][col] != 0) {
                    tmp[tmpRow][col] = grid[row][col];
                    tmpRow--;
                }
            }
        }
 
        // 3) 원본 배열로 다시 값 옮기기
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < n ; j++) {
                grid[i][j] = tmp[i][j];
            }
        }
 
        print();
    }
 
    // 범위 내의 폭탄 터뜨리는 메소드
    private static void pop() {
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < n ; j++) {
                if(inBombRange(i, j)) {
                    grid[i][j] = 0;
                }
            }
        }
    }
 
    private static boolean inBombRange(int x, int y) {
        return (x == r || y == c) &&
                Math.abs(x - r) + Math.abs(y - c) < size;
    }
 
    // 출력용 메소드
    private static void print() {
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < n ; j++)
                sb.append(grid[i][j]).append(" ");
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

 

 

 

➕ 다른 풀이 방식

dx/dy 버전도 있다. (내가 원래 풀려고 했던 방식ㅠ)

import java.util.*;
import java.io.*;
 
public class Main {
    static int n;
    static int[][] grid;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        grid = new int[n][n];
 
        StringTokenizer st;
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++){
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        } 
 
        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken()) - 1;
        int c = Integer.parseInt(st.nextToken()) - 1;
        
        //1. 제거
        pop(r, c);
 
        //2. 중력 적용하기
        for(int i = 0; i < n; i++){
            down(i);
        }
 
        print();        
    }
 
    public static void down(int c){
        int[] temp = new int[n];
        int idx = n-1;
 
        //1. temp 배열에 복사
        for(int i = n-1; i >= 0; i--){
            if(grid[i][c] != 0){
                temp[idx--] = grid[i][c];
            }
        }
 
        //2. grid에 값 넣기
        for(int i = 0; i < n; i++){
            grid[i][c] = temp[i];
        }
    }
 
    public static void pop(int r, int c){
        int[][] dist = {{0, 0}, {-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 자신 + 상하좌우
        int target = grid[r][c]; //범위
 
        for(int k = 0; k < target; k++) {
            for(int i = 0; i < dist.length; i++) {
                int nx = r + dist[i][0] * k;
                int ny = c + dist[i][1] * k;
 
                if(nx < 0 || nx >= n || ny < 0 || ny >= n)  continue;   // 범위 확인
                grid[nx][ny] = 0;
            }
        }
    }
 
    private static void print() {
        StringBuilder sb = new StringBuilder();
 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                sb.append(grid[i][j]).append(" ");
            }
            sb.append("\n");
        }
 
        System.out.println(sb.toString());
    }
}

 

---

💦 어려웠던 점

- 분명 로직 맞게 썼는데 자꾸 원하는 크기만큼 폭발이 안 되길래 코드 다른 거 제출했다가 다시 돌아와서 제출했더니 그 코드가 맞았다.... 이게 뭘까

- 맨해튼 거리 오랜만에 듣다..

 

 

🧐 새로 알게 된 내용

2차원 격자 안에서 터지고 떨어지는 경우

: 2차원 임시 배열을 생성해 중력 적용 시, 각 열마다 아래에서부터 위로 열을 채운다. 그리고 나서 완성된 임시 배열의 값을 원본 배열에 적용한다.

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리 격자 안에서 터지고 떨어지는 경우