[BaekJoon] 1184 귀농 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int size;
    static int[][] profits;
    // 한 점을 기준으로 (왼쪽 위, 오른쪽 아래), (왼쪽 아래, 오른쪽 위) 두 경우에 대해 각각의 땅을 사이즈별로 나눠서 합을 구할 것이다
    // 이때 이동하는 방향을 나타내는 변수이다(인덱스 0부터 왼쪽 아래, 오른쪽 아래, 왼쪽 위, 오른쪽 위)
    static int[][] direction = {{1, -1}, {1, 1}, {-1, -1}, {-1, 1}};
    // 사이즈를 늘리면서 누적합을 구해나가는데, 확장의 시작점을 구하기 위한 기준을 나타내기 위한 변수
    static int[][] startDirection = {{0, 0}, {0, 1}, {-1, 0}, {-1, 1}};

    static void input() {
        Reader scanner = new Reader();

        size = scanner.nextInt();
        profits = new int[size + 1][size + 1];

        for(int row = 1; row <= size; row++) {
            for(int col = 1; col <= size; col++) {
                profits[row][col] = scanner.nextInt();
            }
        }
    }

    static void solution() {
        int answer = 0;

        // (왼쪽 위, 오른쪽 아래), (왼쪽 아래, 오른쪽 위)로 땅을 나눌 수 있는 점들은 정해져있다
        // 그 점들 각각을 순회하면서 해당 점에서 나눌 수 있는 경우의 수를 구하여 누적한다
        for(int row = 2; row <= size; row++) {
            for(int col = 1; col < size; col++) {
                answer += findDividedLandNum(row, col);
            }
        }

        System.out.println(answer);
    }

    static int findDividedLandNum(int x, int y) {
        int sameSumNum = 0;

        // 특정 점에서 (왼쪽 위, 오른쪽 아래), (왼쪽 아래, 오른쪽 위) 두 경우에서 땅을 나눌 수 있는 경우의 수를 각각 구하여 누적한다
        for(int dir = 0; dir < direction.length / 2; dir++) {
            // 왼쪽 아래 혹은 왼쪽 위에 해당하는 땅에서 나올 수 있는 모든 사이즈에서 나타날 수 있는 수익의 합을 모두 구한다
            List<Integer> leftLand = getProfitSum(x + startDirection[dir][0], y + startDirection[dir][1], dir);
            // 오른쪽 아래 혹은 오른쪽 위에 해당하는 땅에서 나올 수 있는 모든 사이즈에서 나타날 수 있는 수익의 합을 모두 구한다
            List<Integer> rightLand = getProfitSum(x + startDirection[(direction.length - 1) - dir][0], y + startDirection[(direction.length - 1) - dir][1], (direction.length - 1) - dir);

            // 왼쪽, 오른쪽 각각의 수익의 합에서 같은 수익의 합이 있다면 그 경우는 땅을 나눌 수 있는 경우이므로 그때의 경우의 수를 누적한다
            for(int leftSum : leftLand) {
                for(int rightSum : rightLand) {
                    if(leftSum == rightSum) {
                        sameSumNum++;
                    }
                }
            }
        }

        return sameSumNum;
    }

    static List<Integer> getProfitSum(int x, int y, int dir) {
        // 모든 수익의 합을 구하기 위해 특정 점을 기준으로 가장 가까운 점에서 왼쪽 위나 왼쪽 아래/오른쪽 위나 오른쪽 아래에 해당하는 땅에 대해 왼쪽/오른쪽으로 누적합을 구한다
        // 누적합을 구할 때, 각 행의 가장 왼쪽/오른쪽을 기준으로 각 행에 대해 누적합을 구하는데, 아래에서 위로/위에서 아래로 올라가며/내려가며 같은 열에 해당하는 값들은 누적해나간다
        int[][] prefixSum = new int[size + 1][size + 1];
        List<Integer> profitSum = new ArrayList<>(); // 모든 사이즈에서 나올 수 있는 수익의 합을 저장하는 리스트

        // 누적합을 구하고 이를 통해 모든 사이즈에서 나올 수 있는 모든 수익의 합을 리스트에 저장한다
        for(int row = x; direction[dir][0] > 0 ? row <= size : row > 0; row += direction[dir][0]) {
            int eachRowSum = 0;

            for(int col = y; direction[dir][1] > 0 ? col <= size : col > 0; col += direction[dir][1]) {
                eachRowSum += profits[row][col];

                prefixSum[row][col] = prefixSum[row - direction[dir][0]][col] + eachRowSum;
                profitSum.add(prefixSum[row][col]);
            }
        }

        return profitSum;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}