[JAVA] 백준 2569 짐정리

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

 

그리디가 메인인 문제인 줄 알고 풀었으나, 알고보니 사이클 관련 문제였다...그래도 그리디가 있긴 하지만..뭔가 찜찜..

문제분석

처음엔 그리디에 초점을 두고, 부분 최적해를 찾으려 고군분투했다. '이동 비용이 가장 작은 해', '무조건 최소값을 이용'... 하지만 모두 반례가 존재했고, 오답이였다.

사이클 규칙을 찾아야 하는 문제였고, 사이클들을 해결해나가다 보면 모든 값을 사이클에 넣을 수 있고 문제를 해결할 수 있는 문제였다. 따라서, 부분 최적해는 '사이클을 찾아서, 비용을 추가해나아가기-모든 값이 사이클중 하나에 포함될 때 까지' 였다. 단, 몇가지 조건을 신경써야 한다.

사이클 존재

이 문제에 맞게 짐을 재배치하는 과정에서, 사이클이 발생하게 된다. 아래 예시를 보면 알겠지만, 1 따로, 400,100,200,300 따로 짐을 옮기게 된다(물론 정답은 아니지만, 사이클의 존재 여부를 보여주기 위함). 이때, 사이클의 존재 여부를 확인하기 위한 arr를 만들어야 한다.

문제를 해결할 때는, 2차원 배열 arr 을 만들고 - [[짐 무게, 정렬 전 인덱스], ...] - 짐 무게 기준으로 정렬하여

정렬 후 idx = arr의 idx

정렬 전 idx = arr의 [idx][1]

로 한번에 확인할 수 있게끔 하였다.

예외사항

이 문제가 골치아픈 이유 중 하나가 예외가 존재한다는 것이다. 위 예시를 보면, 1을 배제하고 100~400이 자리를 바꾸면 최소값이 나올 것  같지만 전혀 그렇지 않다. 100~400만 이용한다면 나오는 최소값은 300+400+500=1200 이다.

하지만 1을 100과 바꾸고, 1을 활용해 자리를 전부 바꾼후 다시 1을 원위치 시켜도 101+201+301+401+101=1105 이다.

따라서, 외부 값 중 최소값을 사용해서 자리를 전부 바꾸는 비용과, 내부 값 만으로 자리를 바꾸는 비용 중 최소값을 비용에 추가해야 한다.

 

제출 코드

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][2]; // [[짐 무게, 정렬 전 인덱스], ...]

        for(int i = 0; i < N ; i++){
            int lug = Integer.parseInt(br.readLine());
            arr[i][0]=lug;
            arr[i][1]=i;
        }
        Arrays.sort(arr,(a,b)->a[0]-b[0]);

        int[] visited = new int[N];
        
        Arrays.fill(visited,0);//0이면 미방문, 1이면 방문

        int price = 0;

        for(int i = 0; i < N; i++){
            if(visited[i]==1){
                continue;
            }else{
                int next = i;
                int cycle = 0;
                while(visited[next]==0){
                    price += arr[next][0];
                    visited[next]=1;
                    next = arr[next][1];
                    cycle += 1;
                }
                price += Math.min(arr[i][0] * (cycle - 2), arr[0][0] * (cycle+1) + arr[i][0]);
            }
        }
        bw.write(String.valueOf(price));
        bw.newLine();
        bw.flush();
        bw.close();


    }
}