24129 : 貫きピラミッド (Pyramid) - JAVA

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

24129번: 貫きピラミッド (Pyramid)

내 기준 예상 외의 방법으로 풀린 문제이다.

지문을 구글의 도움을 받아 해석해보니 이차원 배열 격자에 중심에 높이대로 쌓고 그 주위는 -1하는 구조로 진행되는 문제였다.

당연히 팔방향 bfs 문제라 생각하고 그렇게 풀고 있었다. 값의 대소를 비교하여 큰 피라미드 높이로 피라미드를 갱신하는 방법을 생각하다가 피라미드를 갱신하고자 고민했다.

 

양 피라미드가 있으면, 피라미드의 높이를 분배하면서 충돌하는 부분은 더 큰 것을 부여하도록 설정해서 이 방법을 해결했으며, 의외로 백준 내에 있는 배열 돌리기 문제가 있어서 여기서 풀었던 아이디어를 이용했기에 비교적 빠르고 간단하게 끝난 문제이다. 그렇게 상하좌우를 전부 돌아줬다.

 

뜬금없는 방법으로 해결은 했지만, bfs로도 곧 풀어서 올리겠다.

 

반복문

import java.util.*;
import java.io.*;
public class sol061 {
	static int[][] map;
	static int w, h, n;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		w = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		long res = 0;
		map = new int[h+1][w+1];
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());
			if(map[y][x] < z) {
				map[y][x] = z;
			}
		}
		for(int i = 0; i < h; i++){
            for (int j = 0; j < w; j++) {
                if(i >= 1) {
                	//당연히 높은 칸에 놓인것보다 1이 작아야 하므로
                    map[i][j] = Math.max(map[i-1][j]-1, map[i][j]);
                }
                if(j >= 1) {
                    map[i][j] = Math.max(map[i][j-1]-1, map[i][j]);
                }
                if(i >= 1 && j >= 1) {
                    map[i][j] = Math.max(map[i-1][j-1]-1, map[i][j]);
                }
            }
        }

        for(int i = h - 1; i >= 0; i--) {
            for(int j = 0; j < w; j++) {
                if(i+1< h) {
                    map[i][j] = Math.max(map[i+1][j]-1, map[i][j]);
                }
                if(j >= 1) {
                    map[i][j] = Math.max(map[i][j-1]-1, map[i][j]);
                }
                if(i+1 < h && j >= 1) {
                    map[i][j] = Math.max(map[i+1][j-1]-1, map[i][j]);
                }
            }
        }

        for(int i = 0; i < h; i++) {
            for(int j = w - 1; j >= 0; j--) {
                if(i >= 1) {
                    map[i][j] = Math.max(map[i-1][j]-1, map[i][j]);
                }
                if(j + 1 < w) {
                    map[i][j] = Math.max(map[i][j+1]-1, map[i][j]);
                }
                if(i >= 1 && j + 1 < w) {
                    map[i][j] = Math.max(map[i-1][j+1]-1, map[i][j]);
                }
            }
        }

        for(int i = h - 1; i >= 0; i--) {
            for(int j = w - 1; j >= 0; j--) {
                if(i + 1 < h) {
                    map[i][j] = Math.max(map[i+1][j]-1, map[i][j]);
                }
                if(j + 1 < w) {
                    map[i][j] = Math.max(map[i][j+1]-1, map[i][j]);
                }
                if(i + 1 < h && j + 1 < w) {
                    map[i][j] = Math.max(map[i+1][j+1]-1, map[i][j]);
                }
            }
        }


		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				res += map[i][j];
			}
		}
		System.out.println(res);
	}
}