BOJ 백준 25826 2차원 배열 다중 업데이트 단일 합

문제 : https://www.acmicpc.net/problem/25826

 

 

[ 문제 요약 ]

• 정사각형과 그 안에 있는 값이 주어지고, 두 점이 주어지면, 해당 구간 안에 숫자들을 지속적으로 더해 나갑니다. 그리고 마지막에 한번 원하는 위치의 두 점이 주어지면, 그 안의 값들을 모두 더한 후 출력합니다.

 

[ 테스트케이스 설명 ]

4 3//  사각형크기(1<=1,000), 질의 수(1<=300,000)
1 1 1 1// 크기만큼 사각형의 기본값이 주어짐(1<=1,000,000)
1 1 1 1
1 1 1 1
1 1 1 1
1 0 0 1 1 1// 1번 쿼리 : 왼쪽위, 오른쪽아래가 주어지며 행, 열 순으로 주어짐
1 0 0 2 2 2
2 0 0 2 2// 2번 쿼리 : 2번쿼리는 딱 한번만 나오며 해당 격자안의 값만 더해서 출력[ 알고리즘 분류 ]

 

[ 알고리즘 분류 ]

• 누적 합
• 스위핑
• 차분 배열 트릭

 

[ 문제 해설 ]

 

이 문제는 1차원 차분 배열을 2차원 차분 배열로 응용만 하면 되는 간단한 문제입니다.

 

두 점을 알 때, 그 격자 안에 있는 모든 위치에 숫자를 더 할 때는, 더하려는 숫자를 4개의 격에만 양, 음수로 찍어두고, for 문을 돌려 가로로 먼저 더하고, 그 후 세로로 한 번 더 더해주면 됩니다. 아래는 표로 예시를 보여주며, 6*6 격자에 (2, 2)부터 (5,5) 안에 있는 모든 격자에 5를 더하는 것을 3단계로 나눠 보여줍니다.

 

(1) 단계 : 4개의 점에 마킹을 합니다. 시작점(2,2)에는 +5를, 시작점 오른쪽에 끝나는 곳에 -5를, 시작점 밑에 끝나는 곳에 -5를, 그 오른쪽에 5를 찍어줍니다. 이렇게 해야 가로 누적합을 하고 세로 누적합을 할 때 값이 상쇄됩니다.

y , x	1	2	3	4	5	6
1
2		5				-5
3
4
5
6		-5				5

 

(2)단계 : 가로로 모두 더함

y , x	1	2	3	4	5	6
1
2		5	5	5	5	0
3
4
5
6		-5	-5	-5	-5	0

 

 

(3) 단계 : 세로로 모두 더함

y , x	1	2	3	4	5	6
1
2		5	5	5	5	0
3		5	5	5	5	0
4		5	5	5	5	0
5		5	5	5	5	0
6		0	0	0	0	0

 

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());// 사각형크기(1<=1,000)
		int M = Integer.parseInt(st.nextToken());// 질의 수(1<=300,000)
		long origin[][] = new long[N + 2][N + 2];
		long diff[][] = new long[N + 2][N + 2]; // 차분 배열
		
		for(int y=1; y<=N; y++)
		{
			st = new StringTokenizer(br.readLine());
			for(int x=1; x<=N; x++)
				origin[y][x] = Integer.parseInt(st.nextToken());
		}
		
		// 구간 질의를 입력받으며 차분 배열 4점에 마킹한다.
		for(int i=1; i<M; i++)
		{
			st = new StringTokenizer(br.readLine());
			st.nextToken();
			int y1 = Integer.parseInt(st.nextToken()) + 1;
			int x1 = Integer.parseInt(st.nextToken()) + 1;
			int y2 = Integer.parseInt(st.nextToken()) + 1;
			int x2 = Integer.parseInt(st.nextToken()) + 1;
			int k = Integer.parseInt(st.nextToken());
			// 차분배열의 네점에 마킹
			diff[y1][x1] += k;
			diff[y1][x2 + 1] -= k;
			diff[y2 + 1][x1] += -k;
			diff[y2 + 1][x2 + 1] += k;
		}
		// 가로만 먼저 돌면서 다더함
		for(int y=1; y<=N; y++)
			for(int x=1; x<=N; x++)
				diff[y][x] += diff[y][x-1];
		// 세로를 돌며 다 더함
		for(int x=1; x<=N; x++)
			for(int y=1; y<=N; y++)
				diff[y][x] += diff[y-1][x];

		// 마지막 목표 값을 입력받아 출력한다.
		st = new StringTokenizer(br.readLine());
		st.nextToken();
		int y1 = Integer.parseInt(st.nextToken()) + 1;
		int x1 = Integer.parseInt(st.nextToken()) + 1;
		int y2 = Integer.parseInt(st.nextToken()) + 1;
		int x2 = Integer.parseInt(st.nextToken()) + 1;
		long result = 0;
		// 해당 위치만 돌며 값을 더함
		for(int y=y1; y<=y2; y++)
			for(int x=x1; x<=x2; x++)
				result += origin[y][x] + diff[y][x];
		
		System.out.print(result);
	}
}