[BOJ21278] 호석이 두마리 치킨 (최단거리, 다익스트라, 플로이드 워셜)

 

 

---

문제 링크

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

21278번: 호석이 두 마리 치킨

 

문제 풀이 

다익스트라 풀이 

건물 중 두 개를 뽑는 조합을 구하고 다익스트라 알고리즘으로 최단 거리를 구한다.

 

- N : 건물의 개수, 노드 수, 최대 100 

- M : 도로의 개수, 간선 수, 최대 N * (N-1)/2 = 4950

- 100개의 건물 중 2개를 뽑는 조합 : 100C2 = 100 * 99 / 2! = 4950

- 다익스트라 알고리즘 시간 복잡도 :  O(ElogV)

- 총 시간 복잡도 : O( 100C2 * ElogV) = O ( 4950 * 4950log100 )     

- 1초에 1억번 연산 가능하다 할 때 충분히 풀이할 가치가 있다. 

- 치킨 집의 조합의 경우 2중 for문으로 간단히 처리 가능하다

 

우선순위 큐를 정의하는 다익스트라 알고리즘 로직을 따로 설명하진 않겠습니다

 

 

플로이드 워셜 풀이 

비용이 모두 1이기 때문에 각 노드별로 다른 노드로 가는 최단 거리를 미리 구하고, 치킨 집 조합에 대해 각 노드별 가장 가까운 치킨 집 비용 합산 및 비교하여 결과값을 구한다

 

- 100개의 건물 중 2개의 치킨집 조합 : 100C2 = 4950

- 플로이드 워셜 시간 복잡도 : O(N^3) = O(1,000,000)

- 총 시간 복잡도 : O(100C2 + N^3)

 

점화식

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 
i -> j로 바로가는 비용과 i -> k -> j 를 거쳐가는 비용 중 최소 비용을 구한다

 

 

제출 코드

4950번의 조합에 대해 매번 다익스트라 수행하기 때문에 힙 메모리를 플로이드 워셜보다 더 많이 차지 함을 확인 가능

위 : 다익스트라 / 아래 : 플로이드 워셜

1) 다익스트라

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int N, M;

    static List<Integer>[] adj;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 건물 수 (노드)
        M = Integer.parseInt(st.nextToken()); // 도로 수 (간선)

        adj = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++) adj[i] = new ArrayList<>();

        // cost는 무조건 1
        for(int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            adj[from].add(to);
            adj[to].add(from);
        }
    }

    static class Info implements Comparable<Info> {
        int idx;
        int cost;

        public Info(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }

        @Override
        public int compareTo(Info other) {
            return cost - other.cost;
        }
    }

    static int dijkstra(int a, int b) {
        Queue<Info> que = new PriorityQueue<>();
        que.add(new Info(a, 0));
        que.add(new Info(b, 0));

        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[a] = 0;
        dist[b] = 0;

        while(!que.isEmpty()) {
            Info cur = que.poll();

            if(dist[cur.idx] < cur.cost) continue;

            for(int next : adj[cur.idx]) {
                if(dist[next] > dist[cur.idx] + 1) {
                    dist[next] = dist[cur.idx] + 1;
                    que.add(new Info(next, dist[next]));
                }
            }
        }

        int result = 0;
        for(int i = 1; i <= N; i++) {
            result = result + (dist[i] * 2);
        }

        return result;
    }

    static void pro() {
        int result = Integer.MAX_VALUE;
        int a = 0;
        int b = 0;
        
        // 치킨집을 두개 고르는 조합
        for(int i = 1; i < N; i++) {
            for(int j = i + 1; j <= N; j++) {
                int total = dijkstra(i, j);
                if(result > total) {
                    a = i;
                    b = j;
                    result = total;
                }
            }
        }

        sb.append(a).append(" ").append(b).append(" ").append(result);
    }

    public static void main(String[] args) throws Exception {
        input();

        pro();

        System.out.println(sb);
    }
    
}

 

2) 플로이드 워셜

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int N, M;

    static int[][] dist;

    static int INF = 101;
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 건물의 개수 (노드)
        M = Integer.parseInt(st.nextToken()); // 도로의 개수 (간선)

        // 최단 거리 정보 초기화
        dist = new int[N + 1][N + 1];
        for(int i = 1; i <= N; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }

        // 양방향 그래프이고, 비용은 모두 1이다
        for(int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            dist[from][to] = 1;
            dist[to][from] = 1;
        }

        // 플로이드 워셜 수행 (각 노드별 다른 노드로 가는 비용 계산)
        for(int k = 1; k <= N; k++) {
            for(int i = 1; i <= N; i++) {
                for(int j = 1; j <= N; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    static void pro() {
        int ans = Integer.MAX_VALUE;
        int a = 0;
        int b = 0;

        for(int i = 1; i < N; i++) {
            for(int j = i + 1; j <= N; j++) {
                int total = 0;

                for(int k = 1; k <= N; k++) {
                    if(k == i || k == j) continue; // i, j치킨집의 경우 

                    int minDist = Math.min(dist[k][i], dist[k][j]); // k 집에서 i,j 치킨집까지 비용 중 가장 적은 비용 선택
                    total += minDist;
                }

                if(total < ans) {
                    ans = total;
                    a = i;
                    b = j;
                }
            }
        }

        sb.append(a).append(" ").append(b).append(" ").append(2 * ans);
    }

    public static void main(String[] args) throws Exception {
        input();

        pro();

        System.out.println(sb);
    }
    
}