[BOJ] 2477: 참외밭 (JAVA)

문제

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

 

여담

처음에는 이동하는 발자국만 생각해서 2차원 배열에 방문한 위치를 표시하고 BFS 탐색을 수행하는 방식으로 진행했다.("전체 크기 - 사각형에 포함되지 않는 영역"을 구하면 된다고 생각했었다. 대체 뭔 생각으로 했는지...?)

 

두 번째는 큰 사각형에서 포함되지 않는 사각형을 빼면 될 것 같다고 생각했다. 최대 가로/세로, 최소 가로/세로 길이를 구해서 계산을 했는데 이는 너무 단편적으로만 생각을 해서 틀렸다. (포함되지 않는 작은 사각형이 포함되는 작은 사각형보다 클 수 있음..!) 

 

결국 다른 풀이를 참고했는데 이렇게 쉽게 풀 수 있는 것을 틀린게 너무 아쉽다..🤦🏻‍♀️

 

풀이

주어진 밭에서 자라는 참외의 수는 (육각형의 넓이 * 1m² 넓이에 자라는 참외의 개수)이므로,  육각형의 넓이를 구하는 문제라고 생각하면 된다.

 

육각형은 큰 사각형에서 작은 사각형을 뺀 것과 같다. 따라서 육각형의 넓이는 큰 사각형의 넓이 - 포함되지 않는 작은 사각형의 넓이이다.

 

큰 사각형의 넓이는 가로 길이의 최댓값 * 세로 길이의 최댓값으로, 쉽게 구할 수 있다. 동쪽이나 서쪽 방향으로 이동하는 경우를 가로, 남쪽이나 북쪽으로 이동하는 경우를 세로라고 생각하면 된다. 

• 동쪽, 서쪽으로 이동하는 경우 ⇒ 가로 길이의 최대값 구하기
• 남쪽, 북쪽으로 이동하는 경우 ⇒ 세로 길이의 최대값 구하기

 

포함되지 않는 작은 사각형의 넓이를 구하기 위해서는 가로 길이와 세로 길이를 알아야 한다. 두 값을 구하는 방법은 다음과 같다.

• 가로 길이 = 최대 세로 길이의 양 옆에 위치한 가로 길이의 차이
• 세로 길이 = 최대 가로 길이의 양 옆에 위치한 세로 길이의 차이

 

코드

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

public class Main {
    static final int MIN = 1, N = 6;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine()); // 1m²의 넓이에 자라는 참외의 개수
        int maxW = 1, maxH = 1, wIdx = -1, hIdx = -1;
        Point[] points = new Point[N];
        for (int i = 0; i < 6; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int direction = Integer.parseInt(st.nextToken()); // 이동 방향(1: 동, 2: 서, 3: 남, 4: 북)
            int length = Integer.parseInt(st.nextToken()); // 이동 길이
            points[i] = new Point(direction, length);
            // 동쪽이나 서쪽으로 움직이는 경우 & 가로의 길이가 최대인 경우
            if ((direction == 1 || direction == 2) && maxW < length) {
                maxW = length;
                wIdx = i;
            }
            // 남쪽이나 북쪽으로 움직이는 경우 & 세로의 길이가 최대 경우
            else if ((direction == 3 || direction == 4) && maxH < length) {
                maxH = length;
                hIdx = i;
            }
        }

        // 포함되지 않는 사각형의 세로 길이 구하기 = 최대 가로 길이의 양 옆에 위치한 세로 길이의 차이
        int h1 = (wIdx - 1 < 0) ? points[N - 1].length : points[wIdx - 1].length;
        int h2 = (wIdx + 1 >= N) ? points[0].length : points[wIdx + 1].length;

        // 포함되지 않는 사각형의 가로 길이 구하기 = 최대 세로 길이의 양 옆에 위치한 가로 길이의 차이
        int w1 = (hIdx - 1 < 0) ? points[N - 1].length : points[hIdx - 1].length;
        int w2 = (hIdx + 1 >= N) ? points[0].length : points[hIdx + 1].length;

        int area = maxW * maxH - (Math.abs(h1 - h2) * Math.abs(w1 - w2));
        System.out.println(area * K);
    }

    static class Point {
        int direction;
        int length;

        public Point(int direction, int length) {
            this.direction = direction;
            this.length = length;
        }
    }
}

---

참고

https://velog.io/@jihun333/%EB%B0%B1%EC%A4%802477-%EC%B0%B8%EC%99%B8%EB%B0%AD-%EC%9E%90%EB%B0%94