(Baekjoon) GreedyAlgorithm - (20) 궁금한 민호

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

1507번: 궁금한 민호

 

민호는 궁금한게 많은가보다 이런걸 다 궁금해하고..

민호가 궁금한건 자신이 각 도시마다 다른도시로 갈때

최소비용을 계산했는데 그것에 따라 최소한의 도로만 건설을 하고싶은것이다.

도시계획에 있어서도 도로건설을 어떻게 하느냐에 최소한의 예산을 사용하고 싶은경우도 있을텐데 그럴때도 이런 계획은 필요하지 않을까 싶다.

 

A에서 D로 갈때 다른곳으로 거쳐가는것보다 같거나 많다면 도로를 만드는것보다는

기존의 도로를 사용하는것이 당연한 이치이다. 왜냐하면 쓸데없이 도로를 만들면 예산이 낭비되기 때문이다.

 

그전에 우선 민호에 대해 생각을 해보자.

민호는 어떻게 지도도 없이 최적의수는 먼저 구했을까?

이미 지도에 도로가 표시 되어있다고 생각을 해보고 가정해본다면 이런식으로 생각을 해볼수가 있다.

 

이런식으로 되어있을경우 A와 B는 직접가는것보다 C라는 도시를 경우해서 가는경우가 더 빠를수있다.

그리고 이러한 지도를 보고 사업계획시에는 필요없는 도로인 AB도로를 제거대상으로 선정가능한 방법이 필요할수도있다.

 

A,B를 직접가는것보다 C를 거쳐서가는것이 더 빠르다면 A,B는 쓸데없는 운영비로 적자가 난다.

(물론 실제에서는 이런식으로 도로를 쉽게 제거불가능할것이다.

왜냐하면 도로가 없으면 산에 있는 시골에 방문하기가 어려워지고, 통행량이 한쪽으로 몰리면 더 악화될수있기때문이다.)

 

실제에서는 아마 어떠한 건물을 짓게되어 해당 도로를 폐쇄하게 될경우의 가능성을 확인해보기 위해서 계산을 한다고 생각하면 좋겠다.

 

민호가 우선 가상의 도로로 생각하고 쓸모없다면 제거한다는 가능성으로 문제를 접근하면 될것같다.

 

그리고 우선 우리는 민호가 본 가상의 도로와 지도가 어떻게 생겼는지 알수가없다. A랑 B랑 실제로 직접가는 경로로 연결이 되어있는지 아니면 C라는 경로를 거쳐서 가는 경로만 있는지를 구분할 방도가 없다. 다만 우리에게 주어진것은 단 하나 최적경로이다. (아마 민호가 노가다로 모든경우의수를 구했나보다...)

 

그렇기 때문에 문제에서는 모든도시가 여러 도로로 다 연결되어있다고 가정을 한다.

그리고 그런도로에서 쓸데없는 도로를 제거하는것이 이 문제의 목적이다.

 

이제 쓸데없는 도로에 대해서 정의를 해야한다.

쓸데없는 도로란 A에서 D로 갈때 2밖에 소요되지 않는다.

다른 방식으로 최적의 경로, 예를들어서 A -> B -> D 로 아무리 빨리가도 14이다.

하지만 A -> D로 갈경우 2밖에 비용이 들지 않기 때문에 이 도로는 유지해야한다.

쉽게말해서, A에서 D로 가는 빠른 경로의 도로가 다른 경로를 거치는것보다 빠르다면 해당 경로는 유지를 시키는것이 좋다.

어떻게 보면은 이것은 도로를 만든다기 보다는 A에서 D로 가는 경로의 문제인것 같기도 하다.

이곳에서는 모든 도로가 있다고 가정한것이니 직접 연결하는것이라고 생각하면 된다.

그러므로 A에서 D로 가는 도로는 유지한다. 

 

0 6 15 2 6
6 0 9 8 12
15 9 0 16 18
2 8 16 0 4
6 12 18 4 0

 

(1-2, 2-3, 1-4, 3-4, 4-5, 3-5)

A -> B , B -> C, C -> D, D -> E, A -> D, C -> E 만 연결하고 나머지 도로를 폐쇄한다면 운영비를 엉청나게 줄일수있다.

 

그러므로 우리는 유용한 도로를 계산해야된다.

다시말하자면 유용한도로란 직접가는것이 돌아가는것보다 같지않고 빠른경우다.

 

A -> B,C,D,E

B -> C,D,E

C -> D,E

D -> E

 

이런식으로 직접가는 경우가 돌아가는 경우보다 빠르다면( <, 미만) 그 도로는 유지

 

A -> B로 따질경우에

A -> {C,D,E}를 거쳐서 -> B 로 가는 경우보다 빠르다면 그 도로는 유지

 

1) A->B의 경우

우선 6보다 작은수를 선정해야한다. 왜냐하면 6이랑 같거나 큰수는 돌아가는것이 의미가 없기 때문이다.

여기서는 A -> D 로가는 경우인 2가있다.

그렇다면 D로 가고 D에서 B로 가는 경우를 구한다. 8이다. 2+8 은 10이니까 이 경우의수는 제거한다.

그렇다면 다른 경우의수를 고려해보자. 

D에서 A로 가는 경우의수는 왔던 경로이기 때문에 고려하지 않는다.

우선 2+X < 6이여야 하기때문에 X가 3이하인것을 고른다.

그렇지만 D에서 어디를 가든 3이하인 숫자는 없다.

그러므로 이 도로는 돌아가는 경우보다 직접 만드는것이 훨씬 좋다.

 

2) A -> C의 경우

A에서 C로 갈때 15이니까 15보다 작은수를 찾는다.

B(6),D(2),E(6)이 있다.

i) B로 갔을 경우

  8이하의 숫자를 탐색한다.

  A를 제외하고 D가 있다.

  D로 이동후

  1이하의 숫자를 탐색한다. -> 없다.

  return 실패;

ii) D로 갔을 경우

  B(8)과 E(4)가 후보

  i) B로 갈경우 

     어디로 가든 15보다 큼

  ii) E로 갈경우 

     어디로 가든 15보다 큼

...

..

.

 

0 6 15 2 6 
6 0 9 8 12 
15 9 0 16 18 
2 8 16 0 4 
6 12 18 4 0

 

 

이런식으로 하되 재귀함수를 쓰면 편할것같다는 생각이 든다.

다음과 같이 알고리즘을 생각해볼수있다.

 

X -> Y 로 갈경우

1) Y로 가는 경우의수보다 작은것들을 찾고

2) Y에 도착하기전에 경우의수가 없을경우 X -> Y 직접연결

2) 만약에 Y에 도착했는데 합이 X -> Y 로 직접가는것보다 같거나 작을경우 X -> Y 도로 필요없음

3) 만약에 Y에 도착했는데 합이 X -> Y 로 직접가는것보다 클경우 X -> Y 도로 만들기.........

..

 

package GreedyAlgorithm;

import java.util.Arrays;
import java.util.Scanner;

public class _1507 {

    static int street[][];
    static boolean visited[];
    static int min;
    static int N;
    static int dap;
    static int no=0;
    static int chso=Integer.MAX_VALUE;
    static int error = 0;
    static void highwway(int i,int c,int j,int sum,int count){
        visited[i] = true;
        // System.out.println(i+","+ j + " sum = " + sum + " min = "+min);
        // for (int k = 0; k < visited.length; k++) {
        //     System.out.print(visited[k]+" ");
        // }
        // System.out.println();
        if(visited[j] == true && min >= sum && count>1){
            System.out.println("sum : "+sum+" street["+c+"]["+j+"] : "+ street[c][j]);
            if(chso >= sum) chso = sum;            
            visited[i] = false;
            return;
        }
        
        for (int k = 0; k < N; k++) {
            if(min >= sum+street[i][k] && street[i][k] != 0 && visited[k]==false){ 
                highwway(k, c, j, sum+street[i][k],count+1);
            }
        }
        
        visited[i] = false;
        

    }

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        street = new int[N][N];
        visited = new boolean[N];
        Arrays.fill(visited,false);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                street[i][j] = sc.nextInt();
            }   
        }

        for (int i = 0; i < N; i++) {
            for (int j = 1+i; j < N; j++){
                min = street[i][j];
                highwway(i, i, j, 0,0);
                System.out.print((i+1)+","+(j+1));
                if(chso == Integer.MAX_VALUE ){
                     System.out.println(" : 건설"); 
                    dap += street[i][j];
                } 
                else if(chso != min){ 
                    System.out.println("min : "+min + " chso : "+chso + "  error");
                    error = 1;
                    chso = Integer.MAX_VALUE;
                    break;
                }
                else{
                    System.out.println(" : 건설"); 
                    dap += street[i][j];
                    chso = Integer.MAX_VALUE;
                }
                System.out.println(chso);
                
                Arrays.fill(visited,false);
            }      
        } 
        
        if(error == 1) System.out.println(-1);
        else System.out.println(dap);
        sc.close();

        

    }
    
}

 

로 풀었으나 코드가 너무 복잡해지고 깔끔하지 않아서 결국 개념공부를 하기로 했다.

불가능한 경우도 있었고 그에따라 최솟값을 지속적으로 변경해주어야 했었다. 그리고 해당 최솟값과 본래 최적화된 값과 같지않으면 -1 을 출력했어야 했다.

사실 불가능한 경우를 고려하지 않았다면 내가 푼방법대로 금방풀었을것이다.

억지로 풀수있었으나 이런식으로 푼다한들 의미있어보이지 않았다.

플로이드 와샬 알고리즘을 사용한다고 한다. 그리고 그전에 다익스트라 알고리즘에 대한 이해가 필요한듯했다.

 

 

https://sudeky.tistory.com/147

(basic) Dijkstra, Floyd warshall

 

어떤곳을 거치던 직접가던 것을 사용하여서(플로이드 와샬 알고리즘) 만들은것을 토대로

다시 거꾸로 도로를 계산하는것이다.

 

 

for(int k = 0 ; k < number ; k++){
            for(int i = 0 ; i < number ; i++){
                for(int j = 0 ; j < number ; j++){
                    if(d[i][k] + d[k][j] < d[i][j])
                        d[i][j] = d[i][k] + d[k][j]; 
                }
            }
        }

플로이드 와샬 알고리즘에서는 한번씩 거쳐가는것이 빠르다면 해당 값을 거쳐가는경로로 수정해주었다.

이말인 즉슨

 

이 도로를 사용해서 빠른길을 만든것을 플로이드 와샬 알고리즘을 사용해서 만들었다면

이미 만들어진것을 거꾸로 할경우 최적의 도로만 나온다는 것이다.

 

1) 플로이드 와샬

 -> 거쳐가는것이 빠르다면 

2) 문제

 -> 거쳐가는것이랑 똑같다면 해당 도로 폐쇄하기,

 -> 거쳐가는것보다 크다면 해당 문제 잘못된 -1 출력

 

package GreedyAlgorithm;

import java.util.Arrays;
import java.util.Scanner;

public class _1507 {

    static int d[][];
    static int N;
    static boolean visited[];

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        d = new int[N][N];
        int a[][] = new int[N][N];
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                d[i][j] = sc.nextInt();
                a[i][j] = d[i][j];

            }
        }


        for(int k = 0 ; k < N ; k++){ // 거치는경로
            for(int i = 0 ; i < N; i++){ // 출발경로
                for(int j = 0 ; j < N ; j++){ // 도착경로

                    if( i == k || j == k) continue; // 출발,도착이 거치는경로랑 같은 경우는 계산하면 안됨
                     								// 그러지 않은경우 전부다 0 으로 출력되는 경우가 발생함

                    if(d[i][j] > d[i][k] + d[k][j]) { // 직접가는게 더 큰경우는 제공된것이 가장 빠른길이 아닌경우가 존재하는경우임
                    									// 그러니까 이미 모순되었다는 뜻
                        System.out.println(-1);
                        return;
                    }

                    if(d[i][k] + d[k][j] == d[i][j]) // 거쳐가는것이 기존것과 같다면 a[i][j]에 0 으로 저장해서 해당길은 폐쇄하기
                        a[i][j] = 0;
                }
            }
        }

        int sum = 0;
        for(int i = 0 ; i < N ; i++){
            for(int j = i ; j < N ; j++){
                sum += a[i][j];
            }
        }


        System.out.println(sum);


        sc.close();
        

        
        

    }
    
}

 

플로이드 와샬 알고리즘에서 조금만 수정해주면 된다.

사실 근데 플로이드 와샬 알고리즘을 모른다면 너무 복잡하게 풀수밖에 없는 문제인것같다.

개념이 중요한건 알지만 너무 개념적인 문제라 아쉬웠다.

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study