[백준] 21278번 호석이 두 마리 치킨

문제링크: 백준 21278 호석이 두 마리 치킨

---

1. 아이디어

각 노드별로 모든 노드까지의 최단거리를 구한 후에 완전탐색으로 2가지 지점에 치킨집을 차렸을 때의 최단거리의 합을 구하여, 가장 작은 수의 조합을 출력함.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
    static ArrayList<ArrayList<Node>> graph;
    static int[] distanceDP;
    static int[][] dijGraph;
    static int idx;
    
    static class Node {
        int from;
        int to;
        public Node(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }

    public static void dij(int N, ArrayList<Node> nodeArrayList, int start) {
        graph = new ArrayList<>();
        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
        }
        // 양방향 연결함. 양방향 가중치가 다른 경우 단방향으로 연결해야 할 수 있음.
        for (int i = 0; i < nodeArrayList.size(); i++) {
            graph.get(nodeArrayList.get(i).from).add(new Node(nodeArrayList.get(i).to, 1));
            graph.get(nodeArrayList.get(i).to).add(new Node(nodeArrayList.get(i).from, 1));
        }

        distanceDP = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            distanceDP[i] = Integer.MAX_VALUE;
        }
        distanceDP[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.to - y.to);
        pq.offer(new Node(start, 0));

        while(!pq.isEmpty()) {
            Node curNode = pq.poll();
            if(distanceDP[curNode.from] < curNode.to) {
                continue;
            }
            for (int i = 0; i < graph.get(curNode.from).size(); i++) {
                Node adjNode = graph.get(curNode.from).get(i);
                if(distanceDP[adjNode.from] > curNode.to + adjNode.to) {
                    distanceDP[adjNode.from] = curNode.to + adjNode.to;
                    pq.offer(new Node(adjNode.from, distanceDP[adjNode.from]));
                }
            }
        }
        for (int i = 1; i <= N; i++) {
            dijGraph[idx][i] = distanceDP[i];
        }
        idx++;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        dijGraph = new int[N + 1][N + 1];
        idx = 1;

        ArrayList<Node> nodeArrayList = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            nodeArrayList.add(
                new Node(Integer.parseInt(st2.nextToken()), Integer.parseInt(st2.nextToken()))
            );
        }

        for (int i = 1; i <= N; i++) {
            dij(N, nodeArrayList, i);
        }

        int answer = Integer.MAX_VALUE;
        int[] ans = new int[2];

        for (int i = 1; i < N; i++) {
            for (int j = i + 1; j <= N; j++) {
                int sum = 0;
                for (int k = 1; k <= N; k++) {
                    int tmp = Math.min(dijGraph[k][i], dijGraph[k][j]);
                    sum += tmp * 2;
                }
                if(sum < answer) {
                    answer = sum;
                    ans[0] = i;
                    ans[1] = j;
                }
            }
        }

        System.out.println(ans[0] + " " + ans[1] + " " + answer);
    }
}

• 학습내용

  • 가중치가 음이 아니면 다익스트라 사용 가능!
    • 한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있음.

  • 최단경로 알고리즘의 알고리즘 복잡도

    • V: 노드 수, E: 간선 수

    • 다익스트라: O(ElogV)

    • 벨만포드: O(VE)

    • 플로이드-워셜: O(V^3)

• 다른 풀이 (스터디원)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static int M;
    static int[][] graph;
    static int ans = Integer.MAX_VALUE;
    static int[] ansArr = new int[]{1,2};
    static int INF = 999999999;

    public static void main(String[] args) throws Exception{
        input();
        calcDistance(); // 모든 정점까지 거리 구하기
        // i, j번째 치킨집 차리고
        for (int i = 1; i <= N-1; i++) {
            for (int j = i+1; j <= N; j++) {
                // temp는 i번 j번에 치킨집이 있을때 이동 경로의 합
                int temp = solve(i, j);
                if (temp < ans) {
                    ansArr = new int[]{i, j};
                    ans = temp;
                }
            }
        }

        System.out.println(ansArr[0] + " " + ansArr[1] + " " + ans);
    }

    private static int solve(int i, int j) {
        int sum = 0;
        for (int x = 1; x <= N; x++) {
            int temp = Math.min(graph[x][i], graph[x][j]);
            sum += temp * 2;
        }
        return sum;
    }

    private static void calcDistance() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
    }


    private static void input() throws Exception{
        StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        graph = new int[N+1][N+1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(bufferedReader.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) continue;
                if (graph[i][j] != 1) {
                    graph[i][j] = INF;
                }
            }
        }
    }
}

---

마지막 수정일시: 2022-11-21 12:26