문제
https://www.acmicpc.net/problem/5549
풀이 방법
본 문제의 시간 제한은 1초라는 것을 염두해두고 문제를 풀어야 한다.
이 문제를 풀 때, 가장 기본적인 방법으로 풀게되면 시간제한 때문에 통과할 수 없게 된다.
가장 기본적인 방법이란, 모든 값(땅의 정보)을 Map에 저장받고, 테스트 케이스 만큼 좌표를 입력 받아 좌표를 탐색하여 count 한 후 출력하는 방식이다. (기본적인 bfs/dfs 누적합)
이와 같이 구현하면, 좌표가 지정되어 있고 그 부분만 반복하여 값을 찾으면 되기 때문에 시간초과가 발생하지 않을 것이라 생각할 수 있지만 최악의 조건을 생각해 보면 아니라는 것을 알 수 있다.
N,M이 최대 크기인 1,000, K의 최대 크기인 100,000을 입력 받고 모든 케이스가 (1,1) 부터 (1000,1000) 까지 탐색하는 경우 걸리는 시간에 대해 생각해보면 알 수 있을 것이다.
따라서, 이 문제는 이와 같이 푸는 것이 아니라 다른 방법을 사용해야 한다.
여기서 map에 해당 위치가 어떤 종류의 땅이라는 것을 입력 받는 것이 아니라, 해당 열 까지 탐색하면서 존재하는 땅의 3가지 종류의 값을 모두 저장하도록 하였다.
이 때, 모든 열에 대한 것이 아니라 해당 열 까지의 값이기 때문에 for문에서 값을 조금 다르게 계산한다. 2행 4열의 값이라면, 5열 이후에 있는 값들은 모두 무시하고, 4열가지의 모든 값을 저장하게 되는 것이다.
즉, map[4][5]에는 (0,0)부터 (4,5)까지 탐색하면서 나온 각 종류의 땅의 갯수를 합쳐서 [4][5][0~2]에 값을 저장하였다.
0번 index는 정글, 1번 index는 바다, 2번 index는 얼음 땅의 갯수를 저장한다.
이와 같이 땅의 갯수를 저장하도록 구현하기 위해서 입력을 받을 때 열에 대한 for문을 2번 반복하였다.
-
우선 입력을 받을 때 해당 행에서 이전 값을 그대로 가져온 후, 현재 위치에 대한 정보를 저장하도록 하였다.
-
이렇게 되면 이전 행에서의 값을 갱신할 수 없으므로 해당 행에 대한 정보를 갱신 한 후에, 한번 더 for문을 반복하여 이전 행에 대한 값들을 현재 행에 더하는 연산을 하였다.
물론, 한번에 이 두가지를 같이 하게 되면 값이 전혀 다른 값이 되기 때문에 나누어서 연산을 수행해야 한다.
이와 같은 for문을 반복하게 되면, 각 위치에는 각 위치까지 탐색했을 때 땅의 종류의 갯수들이 각각 저장되어 있다. 따라서, 좌표를 입력 받은 후에 해당 좌표에 해당하는 땅의 종류만 구하면 된다.
이 부분에 대해서는 조금 생각해 보면 구하는 방법을 알 수 있을 것이다.
다음 그림을 보고 설명하겠다.
이 그림은 5549번 문제의 힌트에서 가져왔다.
그림에서 빨강, 파랑, 검정 색으로 표시를 따로 해두었는데, 이 그림을 보면 구하는 방법을 알 수 있을 것이다.
우선 (2,2)에서 (3,6) 범위의 땅의 종류를 구하는 것의 예시이다.
우리는 (3,6) 까지의 모든 땅의 갯수를 알고 있다. 따라서 (3,6)값에서 범위 밖의 땅의 갯수들을 제거하면 되는 것이다.
이것을 알고 그림을 보면, 범위 밖은 빨간색과 파란색 펜으로 표시해둔 부분이라는 것을 쉽게 알 수 있을 것이고
검은색 동그라미로 표시한 부분은 중복되서 제거되는 것을 알 수 있다.
즉, [3,6]위치에서 [1,6]과 [3,1]을 뺀 후 중복해서 빠진 [1,1]을 한번 더하면 된다는 것이다.
입력받은 좌표가 s1,s2 ,e1,e2라고 생각했을 때, 이것을 수식으로 표현하면 다음과 같다.
map[e1][e2] - map[s1-1][e2] - map[e1][s2-1] + map[s1-1][s2-1]
3개의 종류의 모든 값을 알아야 하기 때문에, 위의 수식에서 사용된 map 배열에 마지막 3차원 값을 추가하고, 0 ~ 2를 넣는다면 3종류의 값을 모두 구할 수 있다.
그 후, 그 값들을 출력하게 되면 시간초과 없이 문제를 해결할 수 있다.
코드
package day0220;
import java.io.*;
import java.util.*;
public class BOJ_G5_5549_행성탐사 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
int T = Integer.parseInt(br.readLine());
int[][][] map = new int[R+1][C+1][3]; // map[r][c][땅의 종류] : 각 위치에는 각 위치까지 탐색했을 때 땅의 종류의 개수들이 저장.
for(int i=1; i<=R; i++) {
String input = br.readLine();
for(int j=1; j<=C; j++) {
for(int k=0; k<3; k++) {
map[i][j][k] = map[i][j-1][k]; // 이전 열의 값을 저장
}
char tmp = input.charAt(j-1);
if(tmp == 'J') map[i][j][0]++;
else if(tmp == 'O') map[i][j][1]++;
else map[i][j][2]++;
}
for(int j=1; j<=C; j++) {
for(int k=0; k<3; k++) {
map[i][j][k] += map[i-1][j][k]; // 이전 행의 값을 더함.
}
}
}
int[] ans = new int[3];
for(int t=0; t<T; t++) {
st = new StringTokenizer(br.readLine());
int r1 = Integer.parseInt(st.nextToken());
int c1 = Integer.parseInt(st.nextToken());
int r2 = Integer.parseInt(st.nextToken());
int c2 = Integer.parseInt(st.nextToken());
for(int i=0; i<3; i++) { // 구하려는 좌표에서 (이전행의 해당 열까지의 값)과 (이전열의 해당 행까지의 값)을 빼고 중복값을 더해줘서 구한다.
ans[i] = map[r2][c2][i] - map[r1-1][c2][i] - map[r2][c1-1][i] + map[r1-1][c1-1][i];
}
System.out.println(ans[0]+" "+ans[1]+" "+ans[2]);
}
}
}