[백준 11660번] 구간 합 구하기 5 - python

문제 링크

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

11660번: 구간 합 구하기 5

풀이 

- bfs로 풀었는데 시간 초과 발생. dp로 풀어야 하는 듯하다 

# 시간 초과
from collections import deque 
import sys
input = sys.stdin.readline 

dx = [ 1, -1 , 0, 0 ]
dy = [ 0, 0, 1, -1 ]

def bfs(a,b):
  result = graph[a][b]
  q = deque()
  q.append((a,b))
  visited[a][b] = True

  while q:
    x, y = q.popleft()
    
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if x1-1 <= nx < x2 and y1-1 <= ny < y2 and not visited[nx][ny]:
        result += graph[nx][ny]
        visited[nx][ny] = True
        q.append((nx,ny))

  return result 
  
n, m = map(int,input().split())

graph = []

for _ in range(n):
  graph.append(list(map(int,input().split())))

for _ in range(m):
  x1, y1, x2, y2 = map(int,input().split())

  visited = [ [False] * n for _ in range(n)]

  print(bfs(x1-1, y1-1))

- num_sum[i][j]는 좌표(i,j)까지의 누적합 

누적합은 

num_sum[i][j] = graph[i-1][j-1] + num_sum[i-1][j] + num_sum[i][j-1] - num_sum[i-1][j-1] 로 구할 수 있다. 

 - (x1, y1)부터 (x2, y2)까지의 합은 

result = num_sum[x2][y2] - num_sum[x1 - 1][y2] - num_sum[x2][y1 - 1] + num_sum[x1 - 1][y1 - 1] 

import sys
input = sys.stdin.readline 
  
n, m = map(int,input().split())

graph = []

for _ in range(n):
  graph.append(list(map(int,input().split())))

num_sum = [ [0] * (n+1) for _ in range(n+1)]

for i in range(1,n+1):
  for j in range(1,n+1):
    num_sum[i][j] = graph[i-1][j-1] + num_sum[i-1][j] + num_sum[i][j-1] - num_sum[i-1][j-1]

for _ in range(m):
  x1, y1, x2, y2 = map(int,input().split())
  
  result = num_sum[x2][y2] - num_sum[x1 - 1][y2] - num_sum[x2][y1 - 1] + num_sum[x1 - 1][y1 - 1]

  print(result)

- 2022.04.12 다시 풀이 

import sys
input = sys.stdin.readline 

n, m = map(int,input().split())

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))
    
data = [ [0] * n for _ in range(n) ] 

data[0][0] = graph[0][0]
# 가로 첫째줄 
for i in range(1,n):
    data[0][i] += data[0][i-1] + graph[0][i]

# 세로 첫째줄 
for j in range(1,n):
    data[j][0] += data[j-1][0] + graph[j][0]
    
# 누적해서 더하기 
for i in range(1,n):
    for j in range(1,n):
        data[i][j] += data[i-1][j] + data[i][j-1] - data[i-1][j-1] + graph[i][j]

for _ in range(m):
    x1, y1, x2, y2 = map(int,input().split())
    result = data[x2-1][y2-1]
    if 0 <= x1-2 < n :
        result -= data[x1-2][y2-1] 
    if 0 <= y1-2 < n :
        result -= data[x2-1][y1-2]
    if 0 <= x1-2 < n and 0 <= y1-2 < n:
        result += data[x1-2][y1-2]
    print(result)