[BOJ / Python] 5549번: 행성 탐사

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

5549번: 행성 탐사

 

문제

 

풀이

n이라는 배열에 지도의 크기 M과 N을 각각 저장하고, qn에는 조사 영역의 개수를 입력받는다. 지도의 내용은 data배열에 저장하는데, 지역은 정글, 바다, 얼음으로 총 3 종류이므로 data배열과 크기가 같은 배열 jdata, odata, idata를 생성한다. data에 값을 입력받는 동시에 해당 위치의 영역이 J라면 jdata에, O라면 odata에, I라면 idata에 1을 입력하도록 한다. 마지막으로 q라는 배열을 만들어 조사 영역의 범위들을 입력하도록 한다.

위의 그림 중 가운데 표는 문제에 나와있는 예제에서 jdata를 추출해낸 표이다. 이 문제를 누적합으로 풀기 위해서는 오른쪽 표와 같이 jdata값을 해당 위치까지 점차적으로 더해가는 표가 필요한데, 이를 jd라고 정한다. odata에 대한 표는 od, idata에 대한 표는 id라고 하고, 같은 방식으로 표를 생성한다. 이 표를 이용하여 각 조사영역에서의 영역 종류 개수를 출력하도록 하는데, (x1,y1), (x2,y2)에서의 영역의 합을 구한다고 한다면 ((x2,y2)까지의 합)-((x1-1,y2)까지의 합)-((x2,y1-1)까지의 합)+((x1-1,y1-1)까지의 합) 으로 구하므로, jd, od, id에서 이 공식을 사용하여 해당 값을 구하도록 한다.

 

코드

input=__import__('sys').stdin.readline
n=[*map(int,input().split())]
qn=int(input())
data=[]
jdata=[[0]*n[1] for _ in range(n[0])]
odata=[[0]*n[1] for _ in range(n[0])]
idata=[[0]*n[1] for _ in range(n[0])]
for i in range(n[0]):
  data.append(input())
  for j in range(n[1]):
    if data[i][j]=='J':
      jdata[i][j]=1
    elif data[i][j]=="O":
      odata[i][j]=1
    else:
      idata[i][j]=1
q=[]
for i in range(qn):
  q.append([*map(int,input().split())])
jd=[[0]*(n[1]+1) for _ in range(n[0]+1)]
od=[[0]*(n[1]+1) for _ in range(n[0]+1)]
id=[[0]*(n[1]+1) for _ in range(n[0]+1)]
for i in range(1,n[0]+1):
  for j in range(1,n[1]+1):
    jd[i][j]=jd[i-1][j]+jd[i][j-1]-jd[i-1][j-1]+jdata[i-1][j-1]
    od[i][j]=od[i-1][j]+od[i][j-1]-od[i-1][j-1]+odata[i-1][j-1]
    id[i][j]=id[i-1][j]+id[i][j-1]-id[i-1][j-1]+idata[i-1][j-1]
for i in range(qn):
  print(jd[q[i][2]][q[i][3]]+jd[q[i][0]-1][q[i][1]-1]-jd[q[i][2]][q[i][1]-1]-jd[q[i][0]-1][q[i][3]],od[q[i][2]][q[i][3]]+od[q[i][0]-1][q[i][1]-1]-od[q[i][2]][q[i][1]-1]-od[q[i][0]-1][q[i][3]],id[q[i][2]][q[i][3]]+id[q[i][0]-1][q[i][1]-1]-id[q[i][2]][q[i][1]-1]-id[q[i][0]-1][q[i][3]])

 

결과