[백준 5549번] 파이썬 - 행성 탐사

백준 5549_행성 탐사

시간 제한 1초, 메모리 제한 256MB

# 조건

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

출력

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

# 접근 방법

• 최대 100,000번의 범위 조사를 해야하므로 브루트 포스로 풀면 시간 초과가 발생한다.
• 따라서 누적합을 이용해서 풀어준다.
• 1, 1부터 시작하므로 0행과 0열을 임의로 붙여준다.
• DP 배열은 [0, 0, 0]을 각 좌표마다 할당해주면서 1, 1부터 현재 좌표까지의 J의 개수, O의 개수, I의 개수로 해준다.
• 이 때, DP 점화식은 0~2를 순회하며 현재 발견한 구역은 + 1을 추가로 해주고 아니라면 DP[i][j][arr[i][j]] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]로 해준다.
• 주어진 조사 대상 영역을 출력하는 경우에는 반대로 범위의 가장 마지막 값 a, b, c, d로 받는 경우 dp[c][d]에서 a-1, d와 c, b-1를 빼주고, a-1, b-1 값을 더해 주면 된다.
• https://velog.io/@bb2sol/%EB%B0%B1%EC%A4%80-5549-Python 위 블로그의 그림을 참고하면
• 2번 + 3번의 값을 하면 1번의 값이 중복되어 더해지므로 dp에 기록하는 경우는 2+3-1이 기본 값이 된다.
• 반대로 범위의 값을 구할 때는 4 - 2 - 3에서 중복되어 빼진 1의 값을 더해주면 되는 것이

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N, M = map(int, input().split())  
K = int(input())  
arr = [['0'] * M] + [['0'] + list(input().strip()) for _ in range(N)]  

conv = {'J':0, 'O':1, 'I':2}  

dp = [[[0, 0, 0] for _ in range(M+1)] for _ in range(N+1)]  
for i in range(1,N+1):  
    for j in range(1, M+1):  
        # J, O, I 순서 복사  
        for k in range(3):  
            if conv[arr[i][j]] == k:  
                dp[i][j][k] = dp[i-1][j][k] + dp[i][j-1][k] - dp[i-1][j-1][k] + 1  
            else:  
                dp[i][j][k] = dp[i - 1][j][k] + dp[i][j - 1][k] - dp[i - 1][j - 1][k]  
for _ in range(K):  
    a, b, c, d = map(int, input().split())  
    result = [0, 0, 0]  
    for k in range(3):  
        result[k] = dp[c][d][k] - dp[a-1][d][k] - dp[c][b-1][k] + dp[a-1][b-1][k]  
    print(*result)