[백준 1027번 문제, JAVA] 고층 건물

문제

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.

 

입력:

첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.

---

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] lines = br.readLine().split("\\s+");

        List<Long> views = new ArrayList<>();

        List<Building> buildingList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            buildingList.add(new Building(i, Integer.parseInt(lines[i])));
        }

        for (int i = 0; i < n; i++) {
            // 빌딩은 배열에 넣은 순서대로 선택하여 비교(A빌딩)
            Building aBuilding = buildingList.get(i);

            long leftViewBuilding = 0;
            long rightViewBuilding = 0;

            // 빌딩이 보이는지 확인할 빌딩(B빌딩)은 A빌딩 기준으로 가장 왼쪽에 있는 빌딩부터 비교
            // 먼저 왼쪽 부터 비교
            for (int j = 0; j < i; j++) {
                boolean isView = false;
                Building bBuilding = buildingList.get(j);

                // A빌딩과 B빌딩 사이에 다른 빌딩(C빌딩)이 있어서 보이는지 안보이는지 확인
                // C빌딩은 A빌딩에서 -1 혹은 + 1한 빌딩을 선택하며 B빌딩까지 비교한다
                // C빌딩이 B빌딩과 동일한 빌딩일 경우 A빌딩에서 B빌딩은 보인다

                int specialIndex = -1;
                for (int k = i - 1; k >= j ; k--) {
                    specialIndex++;
                    if (k == j) {
                        if (isView || specialIndex == 0) {
                            leftViewBuilding++;
                        }
                    } else {
                        Building cBuilding = buildingList.get(k);
                        if(aBuilding.isCrossPointUnder(bBuilding, cBuilding)) {
                            isView = true;
                        } else {
                            break;
                        }
                    }
                }

            }

            // 그 다음 오른쪽 비교
            for (int j = buildingList.size() - 1; j > i; j--) {
                boolean isView = false;
                Building bBuilding = buildingList.get(j);

                // 왼쪽에서 한 것과 마찬가지로 진행
                int specialIndex = -1;
                for (int k = i + 1; k <= j ; k++) {
                    specialIndex++;
                    if (k == j) {
                        if (isView || specialIndex == 0) {
                            rightViewBuilding++;
                        }
                    } else {
                        Building cBuilding = buildingList.get(k);
                        if(aBuilding.isCrossPointUnder(bBuilding, cBuilding)) {
                            isView = true;
                        } else {
                            break;
                        }
                    }
                }
            }
            aBuilding.setViewCount(leftViewBuilding + rightViewBuilding);
            views.add(aBuilding.getViewCount());
        }

        System.out.println(Collections.max(views));
    }

    static class Point {
        long x;
        long y;
        Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Building {
        Point landingPoint, roofPoint;
        long viewCount = 0;
        Building(int x, int y) {
            this.landingPoint = new Point(x, 0);
            this.roofPoint = new Point(x, y);

        }

        public long getViewCount() {
            return viewCount;
        }

        public void setViewCount(long viewCount) {
            this.viewCount = viewCount;
        }

        boolean isCrossPointUnder(Building bB, Building cB) {
            Point p1 = this.roofPoint;  // A빌딩 지붕 좌표
            Point p2 = bB.roofPoint;    // B빌딩 지붕 좌표
            Point p3 = cB.roofPoint;    // C빌딩 지붕 좌표

            // 선분 AB의 기울기
            double m = (double) (p2.y - p1.y) / (p2.x - p1.x);
            double b = p1.y - m * p1.x;

            // 선분 AB와 직선 C의 교점의 y좌표가 C의 y좌표 보다 큰지 비교
            // 그래야 빌딩이 보이기 때문
            return m * p3.x + b > p3.y;
        }

    }
}

---

해결

이 문제는 한 빌딩의 옥상에서 가장 많은 다른 빌딩이 보이는지 확인하는 문제이다

가장 높은 빌딩이 가장 많은 빌딩을 볼 수 있지 않은가 라고 생각할 수 있지만

오히려 가장 낮은 빌딩이 가장 많은 빌딩을 볼 수 도 있다.

 

그래서 처음에는 두 선분이 교차하는지 알아보기 위해서 공식을 찾아봤지만 생각보다 어려웠다

시간이 좀 지나고 친구가

비교대상 빌딩의 선분을 직선으로 연장하면 선택한 빌딩과 다른 빌딩이 보이는지 확인하는 선분과교차하지 않는가 그래서 그 교차하는 교점보다 지붕이 낮으면 빌딩이 보인다는 생각을 말해주었고 바로 알고리즘이 떠올랐다

 

막상 이렇게 적어보니까 전혀 이해가 안될것 같지만

이걸 A, B, C, D라는 빌딩으로 설명을 해보면

예를 들어 A에서 D빌딩이 보이는지 확인하려면 어떻게 해야하는가

A와 D사이에 B, C 빌딩이 A와 D를 이은 선분과 교차하거나 접하지 않으면 된다

각 빌딩 사이에 교차하거나 접하지 않은지 확인하려면 B와 C빌딩을 직선으로 연장하고

A와 D 선분과 교점의 Y좌표가 원래 B와 C 빌딩의 옥상 Y좌표와 비교해서

교점이 옥상 Y좌표보다 크면 교차하거나 접하지 않는다

 

그래서 각 빌딩들과 높이를 비교하게 되면 두 개의 점과 하나의 선분이 눈에 보인다

(A~D 빌딩의 좌표는 임의로 설정했다)

먼저 A빌딩의 옥상 점 A(1, 3)과 D빌딩의 옥상점 D(4, 2)를 이으면 선분 AD가 만들어진다

그리고 B와 C 빌딩의 선분을 직선으로 연장한다

 

 

자 그러면 선분 AD와 직선B, C의 교점이 만들어지지 않는가 이 교점과 원래 B빌딩의 옥상 점B(2, 2)와 C빌딩의 옥상 점C(3, 4)와 비교했을 때 원래 옥상의 Y좌표가 교점보다 낮으면 가로막지 않는것이다

 

위의 그림에서 A와 D사이에 B빌딩은 높이가 낮아 상관없지만 C가 높아서 가로막는다

그러면 A와 D가 서로 보이지 않는것이다 

 

우리는 이문제를 풀면서 각 빌딩의 1층좌표와 옥상 좌표를 얻을 수 있다

점두개만 있으면 기울기를 얻을 수 있다

각 빌딩의 직선의 방정식은 Y=0, X=각좌표 즉 X=좌표 이다

 

그러면 선분AD를 직선으로 연장시켜서

직선의 방정식을 구한다

 

 

 

a는 기울기이며 기울기를 구하는 공식은

b는 y절편이다

 

우리는 점 두개를 알고 있기 때문에 기울기를 구할 수 있다

 

 

 

우리는 교점의 x좌표를 알고 있고 기울기도 알았다 그러면 b만 구하면 되겠네

 

 

각 좌표를 넣어주면 우리는 직선의 방정식을 구해서 해당 빌딩이 가리는지 안가리는지 알 수 있다

 

그러면 이제 코드로 노가다만 해주면 된다

 

 

나는 해당 빌딩의 왼쪽과 오른쪽으로 나눠서 비교했다

이 문제는 공식을 제대로 사용만 하면 풀 수 있기 때문에 공식을 제대로 점검해야한다

 

---

참고

링크