[백준] 5549번 : 행성 탐사 Gold5(골드5) - JAVA[자바]

[Gold V] 행성 탐사 - 5549

문제 링크

성능 요약

메모리: 81220 KB, 시간: 624 ms

분류

누적 합

제출 일자

2024년 6월 8일 13:07:06

문제 설명

상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이 행성에서 거주 할 수 있는 구역의 지도를 만들어 지구로 보냈다.

상근이가 보내온 지도는 가로 Ncm, 세로 Mcm 직사각형 모양이다. 지도는 1cm 크기의 정사각형으로 나누어져 있고, 각 구역의 지형이 알파벳으로 표시되어 있다. 지형은 정글, 바다, 얼음 중 하나이며, 정글은 J, 바다는 O, 얼음은 I로 표시되어 있다.

지구에 있는 정인이는 조사 대상 영역을 K개 만들었다. 이때, 각 영역에 정글, 바다, 얼음이 각각 몇 개씩 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 크기 M과 N이 주어진다. (1 ≤ M, N ≤ 1000)

둘째 줄에 정인이가 만든 조사 대상 영역의 개수 K가 주어진다. (1 ≤ K ≤ 100000)

셋째 줄부터 M개 줄에는 상근이가 보낸 지도의 내용이 주어진다.

다음 K개 줄에는 조사 대상 영역의 정보가 주어진다. 정보는 네 정수 a b c d로 이루어져 있다. 구역은 직사각형 모양 이며, 왼쪽 위 모서리의 좌표가 (a, b) 오른쪽 아래 모서리의 좌표가 (c, d)이다.

출력

각 조사 대상 영역에 포함되어 있는 정글, 바다, 얼음의 수를 공백으로 구분해 한 줄에 한 정보씩 출력한다.

 

접근 방법

1. 각 정글, 바다, 얼음마다 누적합을 이용해서 계산 속도를 향상시킨다면 1초안에 가능하다.
-> 값을 입력받으면서 누적합을 계산 해준다 M * N (1000 * 1000) + K만큼 상수시간이 걸린다.(100000)
2. 누적합을 구하는 공식 : map[i][j] = map[i-1][j] + map[i][j-1] -map[i-1][j-1]
3. 그 후 범위만큼 구하는 공식 : map[eX][eY] - map[sX-1][eY] - map[eX][sY-1] + map[sX-1][sY-1]
-> 전체 범위에서 해당 범위에 포함되지 않는 구간은 제외하면서 두번 감소되는 구간(map[0][0] ~ map[sX-1][sY-1)은 다시 한번 더해준다.

 

풀이 코드

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

/**
 * 문제: BOJ_5549_G5_행성탐사
 * 메모리: 81220KB
 * 시간: 624ms
 * 접근 방법
 * 1. 각 정글, 바다, 얼음마다 누적합을 이용해서 계산 속도를 향상시킨다면 1초안에 가능하다.
 * -> 값을 입력받으면서 누적합을 계산 해준다 M * N (1000 * 1000) + K만큼 상수시간이 걸린다.(100000)
 * 2. 누적합을 구하는 공식 : map[i][j] = map[i-1][j] + map[i][j-1] -map[i-1][j-1]
 * 3. 그 후 범위만큼 구하는 공식 : map[eX][eY] - map[sX-1][eY] - map[eX][sY-1] + map[sX-1][sY-1]
 * -> 전체 범위에서 해당 범위에 포함되지 않는 구간은 제외하면서 두번 감소되는 구간(map[0][0] ~ map[sX-1][sY-1)은 다시 한번 더해준다.
 */
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 M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(br.readLine());

        // Input
        int[][][] map = new int[3][N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            String input = br.readLine();
            for (int j = 1; j <= M; j++) {
                for (int k = 0; k < 3; k++) {
                    map[k][i][j] = map[k][i - 1][j] + map[k][i][j - 1] - map[k][i - 1][j - 1];
                }

                char ch = input.charAt(j - 1);
                if (ch == 'J') {
                    map[0][i][j]++;
                } else if (ch == 'O') {
                    map[1][i][j]++;
                } else {
                    map[2][i][j]++;
                }
            }
        }// Input End

        StringBuilder sb = new StringBuilder();
        int sX, sY, eX, eY, jungle, ocean, ice;
        for (int i = 1; i <= K; i++) {
            st = new StringTokenizer(br.readLine());
            sX = Integer.parseInt(st.nextToken());
            sY = Integer.parseInt(st.nextToken());
            eX = Integer.parseInt(st.nextToken());
            eY = Integer.parseInt(st.nextToken());

            jungle = map[0][eX][eY] - map[0][sX - 1][eY] - map[0][eX][sY - 1] + map[0][sX - 1][sY - 1];
            ocean = map[1][eX][eY] - map[1][sX - 1][eY] - map[1][eX][sY - 1] + map[1][sX - 1][sY - 1];
            ice = map[2][eX][eY] - map[2][sX - 1][eY] - map[2][eX][sY - 1] + map[2][sX - 1][sY - 1];

            sb.append(jungle).append(' ').append(ocean).append(' ').append(ice).append('\n');
        }

        System.out.println(sb);
    }
}