[Python] 백준/BOJ 5549번: 행성 탐사 (Gold 5)

💻 Problem

문제 보러 가기

 

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

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

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

 

💡 Approach

누적합으로 풀었다.

16507번(어두운 건 무서워) 문제와 방식은 같다.

 

지형이 정글, 바다, 얼음 세 가지이므로 depth는 3이다.

각 지형의 2차원 배열 안에 누적합을 적용하면 된다.

 

✏️ Solution

import sys
input = sys.stdin.readline

M, N = map(int, input().split()) # 가로, 세로
K = int(input()) # 조사 대상 영역의 개수
TERRAIN = {'J': 0, 'O': 1, 'I': 2} # 지형 정보 매핑
planet = [[[0] * (N + 1) for _ in range(M + 1)] for _ in range(3)] # 행성 지도

for r in range(1, M + 1):
    line = input()
    for c in range(1, N + 1):
        for d in range(3):
            planet[d][r][c] = planet[d][r - 1][c] + planet[d][r][c - 1] - planet[d][r - 1][c - 1]
        planet[TERRAIN[line[c - 1]]][r][c] += 1

for i in range(K):
    r1, c1, r2, c2 = map(int, input().split())
    
    for i in range(3):
        print(planet[i][r2][c2] - planet[i][r1 - 1][c2] - planet[i][r2][c1 - 1] + planet[i][r1 - 1][c1 - 1], end=' ')
    print()

 

⏱️ 시간복잡도

• O(M * N + K)

M * N * 3 + K * 3

= 1,000 * 1,000 * 3 + 100,000 * 3

= 3,000,000 + 300,000

= 3,300,000