[백준] 27115 통신소 [자바]

 

---

https://coder-in-war.tistory.com/entry/%EA%B0%9C%EB%85%90-47-%EC%8A%A4%EC%9C%84%ED%95%91-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Sweeping-Algorithm

[ 개념 ] 47. 스위핑 알고리즘(Sweeping Algorithm)

 

---

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

public class Main {
	static int N,M,K;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		long ans = 0;
		int[][] arr = new int[N][M];
		boolean[][] check = new boolean[N][M];
		for(int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int p = Integer.parseInt(st.nextToken());
			arr[x-1][y-1] = p;
			check[x-1][y-1] = true;
		}
		for(int i = 0; i < N-1; i++) {
			for(int j = 0; j < M; j++) {
				if(arr[i][j] != 0 && arr[i+1][j] <= arr[i][j]-1) {
					arr[i+1][j] = arr[i][j]-1;
					check[i+1][j] = true;
				}
			}
		}
		
		for(int i = N-1; i > 0; i--) {
			for(int j = 0; j < M; j++) {
				if(arr[i][j] != 0 && arr[i-1][j] <= arr[i][j]-1) {
					arr[i-1][j] = arr[i][j]-1;
					check[i-1][j] = true;
				}
			}
		}
		
		for(int j = 0; j < M-1; j++) {
			for(int i = 0; i < N; i++) {
				if(arr[i][j] != 0 && arr[i][j+1] <= arr[i][j] -1) {
					arr[i][j+1] = arr[i][j] - 1;
					check[i][j+1] = true;
				}
			}
		}
		
		for(int j = M-1; j > 0; j--) {
			for(int i = 0; i < N; i++) {
				if(arr[i][j] != 0 && arr[i][j-1] <= arr[i][j] - 1) {
					arr[i][j-1] = arr[i][j] -1;
					check[i][j-1] = true;
				}
			}
		}
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(check[i][j]) ans++;
			}
		}
		System.out.println(ans);
	}
}