[CodeUp/2714] 벌들의 자료구조 (Python)

Problem : https://codeup.kr/problem.php?id=2714&rid=0

Status : Solved

Time : 00:15:16

 

---

 

문제 설명

 

벌집 모양의 자료구조를 상상해 보자.

맨 왼쪽 위의 칸은 (1,1)이다. 초기에는 모든 칸에 0이 저장되어 있다.

당신은 이 형태의 자료구조를 구현하여 여러 개의 연산을 수행해야 한다.

이 형태의 자료구조에서는 (X,Y)에서 오른쪽으로 인접한 칸은 (X,Y+1)이고, 왼쪽 아래로 인접한 칸은 (X+1,Y)이며, 오른쪽 아래로 인접한 칸은 (X+1,Y+1)이다. 위의 설명만으로는 이해가 어려울 수 있으니 (1,1)부터 (4,4)까지의 형태는 아래 그림을 참고하라.

 

 

입력 및 출력

 

입력

첫 번째 줄에는 자료구조의 크기 N과 연산의 수 Q가 주어진다. (N≤500,Q≤2,000)

자료구조의 크기가 N이라는 것은 칸의 좌표 (X,Y)를 고려할 때 항상 X≤N, Y≤N이라는 것이다.

그 뒤 Q개의 줄에 양의 정수 X,Y,R, 정수 K가 주어지며, 이것은 (X,Y)를 포함하여, (X,Y)로부터 R개의 칸을 거쳐 도달하는 모든 칸의 값에 K를 더하라는 것이다. (R≤5,K≤100,000)

마지막 줄에는 X, Y가 주어진다.

 

출력

(X,Y) 칸에 저장된 값을 출력하라.

 

입력 예시

4 2

1 1 1 1

3 2 1 2

2 1

 

출력 예시

3

 

 

---

 

풀이

 

언뜻 보면 부분합 문제로 볼 수 있으나, 출력해야 하는 좌표는 딱 하나이므로 출력 좌표를 중심으로 생각해보면 풀이가 쉬워진다.

1. 경로 탐색 알고리즘으로, 구해야하는 좌표를 기준으로 모든 좌표의 거리를 구한다.

2. 그 다음 쿼리를 처리하게 되는데, 기준 좌표와의 거리가 쿼리에 주어진 거리보다 크다면 결과값에 k값을 더해준다.

 

따라서 더 빠른 시간 내에 풀이할 수 있다.

 

풀이 코드

import sys
from collections import deque
input = sys.stdin.readline

dx = [0, 1, 0, -1, 1, -1]
dy = [1, 0, -1, 0, 1, -1]
N, Q = map(int, input().split())

query_list = [list(map(int, input().split())) for _ in range(Q)]
X, Y = map(int ,input().split())
dist_list = [[float('inf')]*(N+1) for _ in range(N)]
dist_list[Y-1][X-1] = 0
q = deque([(X-1, Y-1, 0)])

while q :
  x, y, dist = q.popleft()
  for i in range(6) :
    ax, ay = x+dx[i], y+dy[i]
    if -1 < ax < N and -1 < ay < N and dist_list[ay][ax] > dist+1 :
      dist_list[ay][ax] = dist+1
      q.append((ax, ay, dist+1))

answer = 0
for x, y, r, k in query_list :
  if dist_list[y-1][x-1] <= r :
    answer += k

print(answer)

풀이 완료!