[Java] 코드트리 / 기울어진 직사각형

기울어진 직사각형

문제

n X n 크기의 격자가 주어졌을 때 직사각형으로 순회를 하였을 때 합이 최대가 되는 값을 구하는 문제이다.

일단 모든 방식을 다 확인해야하기 때문에 브루트포스 와 DFS를 사용하였다.

문제를 풀면서 생각한점은 과연 몇중 for문을 써야지 문제가 풀릴까였다.

일단 모든 좌표를 돌기 위한 변수 i, j 그리고 직사각형의 가로와 세로 길이를 정하기 위한 변수 w, h를 사용하였다.

for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		for (int w = 1; w < n; w++) {
			for (int h = 1; h < n; h++) {
				result = Math.max(result, dfs(i, j, w, h));
			}
		}
	}
}

그 후 구현하는 DFS 함수에 대해서 알아보겠다.

직사각형이기 때문에 가로와 세로의 증가량과 감소량은 같다는 점을 이용해 size 라는 배열을 두고 함수의 인자로 받은 변화량 w, h 를 배열에 번갈아가며 두번씩 넣어주었다.

int[] size = {w, h, w, h};

그 후 직사각형의 대각선 방향을 정하는 dx와 dy 배열을 반복하게 해주는 변수 i를 사용하고 그렇게 되면 오른쪽 위 방향, 왼쪽 위 방향, 왼쪽 아래 방향, 오른쪽 아래 방향이 정해진다.

일단 시작하면 오른쪽 위 방향일텐데 오른쪽 위 방향이 정해졌다면 그 안에서 대각선방향으로 얼마나 갈지 정해줘야 하는데 그건 j 변수를 위에서 만든 size 배열을 사용해 얼만큼 갈지를 정해준다.

그리고 배열의 범위를 벗어났는지 아닌지 체크를 한 후 total 값에 더해주고 해당 total 값을 리턴해주고 가장 큰 값을 출력해주면 된다.

public static int dfs(int x, int y, int w, int h) {
	int[] size = {w, h, w, h};
	int total = 0;

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < size[i]; j++) {
			x += dx[i];
			y += dy[i];

			if (x < 0 || x >= n || y < 0 || y >= n) {
				return 0;
			}
			total += arr[x][y];
		}
	}
	return total;
}

위와 같은 코드를 조합하여 완성된 코드는 아래와 같다.

---

코드

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

public class CodeTree {
    static int n;
    static int[][] arr;
    static int result;
    static boolean[][] visited;
    static int[] dx = {1, -1, -1, 1};
    static int[] dy = {1, 1, -1, -1};

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        arr = new int[n][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int w = 1; w < n; w++) {
                    for (int h = 1; h < n; h++) {
                        result = Math.max(result, dfs(i, j, w, h));
                    }
                }
            }
        }
        System.out.println(result);
    }

    public static int dfs(int x, int y, int w, int h) {
        int[] size = {w, h, w, h};
        int total = 0;

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < size[i]; j++) {
                x += dx[i];
                y += dy[i];

                if (x < 0 || x >= n || y < 0 || y >= n) {
                    return 0;
                }
                total += arr[x][y];
            }
        }
        return total;
    }
}