[백준 - 5549][GOLD 5][해설 X] - 행성 탐사 (JAVA)

 

문제 링크

---

https://www.acmicpc.net/problem/5549

 

문제

---

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

상근이가 보내온 지도는 가로 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)이다.

 

출력

---

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

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    public static int J = 0;    //정글
    public static int O = 1;    //바다
    public static int I = 2;    //얼음

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

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

        int[][][]map = new int[3][M+1][N+1];
        int[][][]preSum = new int[3][M+1][N+1];

        int K = Integer.parseInt(br.readLine());

        Map<Character,Integer> keyMap = new HashMap<>(); //알파벳->인덱스 변경 맵

        keyMap.put('J',J);
        keyMap.put('O',O);
        keyMap.put('I',I);

        //정글, 바다, 얼음 별 맵 생성
        for(int i=1;i<=M;i++){
            String input = br.readLine();

            for(int j=1;j<=N;j++){
                map[keyMap.get(input.charAt(j-1))][i][j] = 1;
            }
        }

        //누적합 생성
        for(int i=1;i<=M;i++){
            for(int j=1;j<=N;j++){
                preSum[J][i][j] = preSum[J][i-1][j] + preSum[J][i][j-1] - preSum[J][i-1][j-1] + map[J][i][j];
                preSum[O][i][j] = preSum[O][i-1][j] + preSum[O][i][j-1] - preSum[O][i-1][j-1] + map[O][i][j];
                preSum[I][i][j] = preSum[I][i-1][j] + preSum[I][i][j-1] - preSum[I][i-1][j-1] + map[I][i][j];
            }
        }

        //누적합을 이용해 범위내 개수 구하기
        for(int i=0;i<K;i++){
            st = new StringTokenizer(br.readLine());

            int startRow = Integer.parseInt(st.nextToken());
            int startCol = Integer.parseInt(st.nextToken());
            int endRow = Integer.parseInt(st.nextToken());
            int endCol = Integer.parseInt(st.nextToken());

            int junglePreSum = preSum[J][endRow][endCol] - preSum[J][startRow-1][endCol] - preSum[J][endRow][startCol-1] +  preSum[J][startRow-1][startCol-1];
            int oceanPreSum = preSum[O][endRow][endCol] - preSum[O][startRow-1][endCol] - preSum[O][endRow][startCol-1] +  preSum[O][startRow-1][startCol-1];
            int icePreSum = preSum[I][endRow][endCol] - preSum[I][startRow-1][endCol] - preSum[I][endRow][startCol-1] +  preSum[I][startRow-1][startCol-1];

            StringBuilder sb= new StringBuilder();
            sb.append(junglePreSum).append(" ").append(oceanPreSum).append(" ").append(icePreSum);

            System.out.println(sb);
        }
    }
}

 

 

실행 결과

---

 

팁

---

• 2차원 누적합을 만들 때 첫번째 행, 첫번째 열의 누적합 연산시 인덱스를 벗어나는 것을 막기 위해 1칸 여유를 두고 만든다.