[JAVA] 백준 2565. 전깃줄

이 글은 읽는데 약 5분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, < 그림 1 >과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.

< 그림 1 >

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.

출력

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

풀이

문제가 말하는 그대로 교차 하지 않기 위한 것을 검사하는데 초점을 맞추면 어떤 선이 교차하는지 여부를 확인해야 하므로 복잡하다. 그러나 여기서 생각을 바꾸면 훨씬 간단해진다.

전체 전선에서 교차되는 전선의 수를 빼면 그 값은 교차하지 않는 전선의 수이므로, 반대로 교차하지 않는 전선을 만든 후 전체 전선의 수에 빼면 우리가 원하는 교차하는 전선의 수가 나온다.

전체전선수 = 교차안하는전선수 + 교차하는전선수
교차하는전선수 = 전체전선수 – 교차안하는전선수

우리는 교차하지 않기 위해 없애햐 하는 전선의 최수 개수를 구해야한다. 즉, 최대한 많은 전선이 교차되지 않고 연결된 상황을 만든 후 전체 전선의 수에서 그 전선들의 개수를 빼면 우리가 원하는 답이 나온다.

이제 우리는 전선을 최대한 많이 겹치지 않게 놓을 때 전선의 개수를 구하면 된다.

코드

int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N+1][2];  // 0=A, 1=B
int[] dp = new int[N+1];

전봇대 정보를 저장할 배열 arr과 전선 개수를 저장할 배열 dp를 생성한다. 전봇대가 1번부터 시작하기 때문에 편의상 배열도 인덱스 0이 아닌 1부터 채우기 위해 배열의 길이는 N+1이다.

dp[i]의 값이 의미하는 것은 1번 부터 i번째 전봇대 까지 겹치지 않고 연결할 수 있는 전선의 최대 개수이다.

for(int i=1; i<=N; i++){
    String[] inputs = br.readLine().split(" ");
    arr[i][0] = Integer.parseInt(inputs[0]);
    arr[i][1] = Integer.parseInt(inputs[1]);
}

전봇대 정보를 입력 받는다. 각 arr[i]에 대해 arr[i][0]에는 연결된 A 전봇대의 번호가, arr[i][1]에는 연결된 B 전봇대의 번호가 저장된다. 이 두 값을 이렇게 하나의 배열에 같이 묶는 이유는 arr을 A전봇대 번호 기준으로 정렬을 할 것인데, A-B값이 서로 같이 연결 되야하기 때문이다.

Arrays.sort(arr, new Comparator<int[]>() {
    @Override
    public int compare(int[] a, int[] b) {
        return a[0] - b[0];
    }
});

A-B전봇대 연결 정보의 배열인 arr을 정렬한다. 정렬은 A전봇대 기준으로 오름차순으로 정렬한다.

for(int i=1; i<=N; i++){
    dp[i] = 1;
    for(int j=1; j<i; j++){
        if(arr[j][1] < arr[i][1]){
            dp[i] = Math.max(dp[i], dp[j]+1);
        }
    }
}

각 A전봇대에 대해서 현재 전봇대 이전에 겹치지 않고 연결할 수 있는 전선의 최대 개수를 dp배열에 저장한다.

Arrays.sort(dp);
sb.append(N - dp[N]);

마지막으로 dp 배열을 오름차순으로 정렬한다. 그러면 겹치지 않고 연결 가능한 최대 전선 개수가 가장 마지막에 갈 것이며, 전체 전선 개수 N에서 이 값을 뺀 것을 출력해주면 된다.

댓글