[java] 구름톤 9일차. 폭탄 구현하기(2)

문제

N*N 크기의 정사각형 모양의 땅이 있다. 땅을 1*1 크기의 작은 땅으로 나누었을 때, 위에서 y번째, 왼쪽에서 x번째에 위치한 땅의 좌표를 (y,x)로 나타낸다. 추가로 모든 땅에는 폭탄 값이라고 하는 값이 있다. 모든 폭탄 값의 초기 값은 0이다. K개의 폭탄을 이 땅 위에 떨어트리려고 한다. 어떤 1*1 크기의 땅 위에 폭탄을 떨어트리게 되면 폭탄이 떨어진 땅과, 그 땅에 상하좌우로 인접한 칸의 폭탄 값에 영향을 끼친다. 폭탄 값이 변하는 정도는 땅의 상태에 따라 다르다.

- N*N 크기의 영역 밖이거나, 땅의 상태가 #이라면 폭탄 값은 변하지 않는다.

- 땅의 상태가 0 이라면 폭탄 값은 1 증가한다.

- 땅의 상태가 @ 이라면 폭탄 값은 2 증가한다.

 

모든 폭탄을 떨어트린 뒤에, 모든 땅의 폭탄 값 중에서 가장 높은 값을 출력해보자.

입력

첫째 줄에 땅의 한 변의 길이 N과 폭탄을 떨어트릴 횟수 K가 공백을 두고 주어진다. 다음 N개의 줄에는 땅의 상태를 나타내는 N개의 문자가 공백을 두고 주어진다. r번째 줄에서 c번째로 주어지는 문자는 (r,c) 좌표에 해당하는 땅의 상태이다. 다음 K개의 줄에는 폭탄을 떨어트릴 땅의 좌표를 나타내는 y,x가 공백을 두고 주어진다. 이는 (y,x) 좌표에 폭탄을 떨어트린다는 의미이다.

- 1 <= N <= 200

- 1 <= K <= 500 000

- 땅의 상태는 0, @, # 중 하나이다.

- 1 <= y,x <= N

- 입력에서 주어지는 모든 수는 정수이다.

출력

모든 폭탄을 떨어트린 뒤에, 모든 땅의 폭탄 값 중에서 가장 높은 값을 출력한다.

---

이 문제를 해결하기 위해서는 시뮬레이션과 누적 합의 개념을 활용하여 구현할 수 있습니다. 각 땅의 초기 폭탄 값은 0이고, 땅의 상태에 따라 폭탄 값이 증가하는 규칙이 정의되어 있습니다. 폭탄을 떨어트릴 때마다 해당 위치와 상하좌우 위치의 폭탄 값에 변화를 주어야 합니다.

아래는 이 문제를 해결하기 위한 간단한 과정을 설명한 것입니다:

1. 입력을 받고 초기 땅의 상태와 폭탄 값 초기화하기:
   • N과 K를 입력받습니다.
   • N x N 크기의 2차원 배열을 생성하고, 땅의 상태에 따라 초기 폭탄 값을 설정합니다. 이 때, 폭탄 값은 0으로 초기화합니다.
2. 폭탄을 떨어트리며 폭탄 값 갱신하기:
   • K번의 반복문을 사용하여 폭탄을 떨어트릴 위치를 입력받습니다.
   • 해당 위치의 땅의 상태를 확인하여 폭탄 값을 적절하게 증가시킵니다.
   • 상하좌우의 위치에 해당하는 땅의 상태가 영향을 받는 경우에도 해당 땅의 폭탄 값을 증가시킵니다.
3. 가장 높은 폭탄 값 찾기:
   • 모든 땅의 폭탄 값을 순회하며 가장 큰 값을 찾습니다.
4. 가장 높은 폭탄 값 출력하기.

이와 같은 접근 방식으로 문제를 해결할 수 있습니다. 단, 이 문제는 입력 범위가 크기 때문에, 누적 합 등을 활용하여 폭탄 값의 변화를 빠르게 처리하는 것이 중요합니다.

 

지피티의 도움으로 어떻게 짤지 고민을 한 다음..

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        String[][] input_board = new String[N][N];
        for (int i = 0; i < N; i++) {
            input_board[i] = br.readLine().split(" ");
        }

        int[][] queries = new int[K][2];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            queries[i][0] = Integer.parseInt(st.nextToken());
            queries[i][1] = Integer.parseInt(st.nextToken());
        }

        solution(N, K, input_board, queries);
    }

    public static void solution(int N, int K, String[][] input_board, int[][] queries) {
        int answer = 0;
        int[][] board = new int[N + 1][N + 1];
        Set<Integer> at = new HashSet<>();
        Set<Integer> sharp = new HashSet<>();

        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++) {
                if (input_board[row][col].equals("@")) {
                    at.add((row + 1) * 1000 + (col + 1));
                }
                if (input_board[row][col].equals("#")) {
                    sharp.add((row + 1) * 1000 + (col + 1));
                }
            }
        }

        int[] dy = {0, -1, 1, 0, 0};
        int[] dx = {0, 0, 0, -1, 1};

        for (int[] query : queries) {
            int y = query[0];
            int x = query[1];
            for (int i = 0; i < 5; i++) {
                int next_y = y + dy[i];
                int next_x = x + dx[i];

                if (0 < next_y && next_y <= N && 0 < next_x && next_x <= N) {
                    if (at.contains(next_y * 1000 + next_x)) {
                        board[next_y][next_x] += 2;
                    } else if (sharp.contains(next_y * 1000 + next_x)) {
                        board[next_y][next_x] += 0;
                    } else {
                        board[next_y][next_x] += 1;
                    }
                }
            }
        }

        for (int row = 1; row <= N; row++) {
            for (int col = 1; col <= N; col++) {
                answer = Math.max(answer, board[row][col]);
            }
        }

        System.out.println(answer);
    }
}

어쩌저찌 해결하긴 했으나.. 타인의 파이썬 코드를 보고 자바로 수정했다.