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

문제

컴공 출신은 치킨집을 하게 되어있다. 현실을 부정하지 말고 받아들이면 마음이 편하다. 결국 호석이도 2050년에는 치킨집을 하고 있다. 치킨집 이름은 "호석이 두마리 치킨"이다.

이번에 키친 도시로 분점을 확보하게 된 호석이 두마리 치킨은 도시 안에 2개의 매장을 지으려고 한다. 도시는 N 개의 건물과 M 개의 도로로 이루어져 있다. 건물은 1번부터 N번의 번호를 가지고 있다. i 번째 도로는 서로 다른 두 건물 Ai 번과 Bi 번 사이를 1 시간에 양방향으로 이동할 수 있는 도로이다.

키친 도시에서 2개의 건물을 골라서 치킨집을 열려고 한다. 이 때 아무 곳이나 열 순 없어서 모든 건물에서의 접근성의 합을 최소화하려고 한다. 건물 X 의 접근성은 X 에서 가장 가까운 호석이 두마리 치킨집까지 왕복하는 최단 시간이다. 즉, "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 최소화할 수 있는 건물 2개를 골라서 치킨집을 열려고 하는 것이다.

컴공을 졸업한 지 30년이 넘어가는 호석이는 이제 코딩으로 이 문제를 해결할 줄 모른다. 알고리즘 퇴물 호석이를 위해서 최적의 위치가 될 수 있는 건물 2개의 번호와 그 때의 "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 출력하자. 만약 이러한 건물 조합이 여러 개라면, 건물 번호 중 작은 게 더 작을수록, 작은 번호가 같다면 큰 번호가 더 작을수록 좋은 건물 조합이다.

입력

 

첫 번째 줄에 건물의 개수 N과 도로의 개수 M 이 주어진다. 이어서 M 개의 줄에 걸쳐서 도로의 정보 Ai , Bi 가 공백으로 나뉘어서 주어진다. 같은 도로가 중복되어 주어지는 경우는 없다. 어떤 두 건물을 잡아도 도로를 따라서 오고 가는 방법이 존재함이 보장된다.

출력

한 줄에 건물 2개가 지어질 건물 번호를 오름차순으로 출력하고, 그때 모든 도시에서의 왕복 시간의 합을 출력한다.

만약 건물 조합이 다양하게 가능하면, 작은 번호가 더 작은 것을, 작은 번호가 같다면 큰 번호가 더 작은 걸 출력한다.

제한

• 2 ≤ N ≤ 100
• N-1 ≤ M ≤ N×(N - 1)/2
• 1 ≤ Ai , Bi​ ≤ N (Ai  ≠ Bi)

풀이

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

class Point {
    int node;
    int cnt;
    Point(int node, int cnt) {
        this.node = node;
        this.cnt = cnt;
    }
}
public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int n, m, p1, p2, min;
    static ArrayList<Integer>[] g;
    static int[][] dist;
    static int[] picked;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        init();
        getDist();
        solve(0, 1);
        System.out.println(p1 + " " + p2 + " " + min);
    }

    static void init() throws IOException {
        min = Integer.MAX_VALUE;
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        dist = new int[n+1][n+1];
        g = new ArrayList[n+1];
        visited = new boolean[n+1];
        picked = new int[2];
        for(int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = stoi(st.nextToken());
            int b = stoi(st.nextToken());
            g[a].add(b);
            g[b].add(a);
        }
    }

    static void solve(int cnt, int start) {
        if(cnt == 2) {
            int sum = 0;
            //세운 치킨 집 마다 모든 건물의 거리 구하기
            for(int i = 1; i <= n; i++) {
                sum += Math.min(dist[picked[0]][i], dist[picked[1]][i])*2;
            }
            if(min == sum) {
                if(p1 == picked[0]) {
                    if(p2 > picked[1]) {
                        p1 = picked[0];
                        p2 = picked[1];
                    }
                } else if(p1 > picked[0]) {
                    p1 = picked[0];
                    p2 = picked[1];
                }
            } else if(min > sum) {
                min = sum;
                p1 = picked[0];
                p2 = picked[1];
            }
            return;
        }

        for(int i = start; i <= n; i++) {
            picked[cnt] = i;
            solve(cnt+1, i+1);
        }
    }
    static void getDist() {
        boolean[][] checked = new boolean[n+1][n+1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == j) {
                    dist[i][j] = 0;
                    checked[i][j] = true;
                    continue;
                }
                if(!checked[i][j]) {
                    dist[i][j] = bfs(i,j);
                    dist[j][i] = dist[i][j];
                    checked[i][j] = true;
                    checked[j][i] = true;
                }
            }
        }
    }

    static int bfs(int a, int b) {
        boolean[] checked = new boolean[n+1];
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(a, 0));
        checked[a] = true;
        while(!q.isEmpty()) {
            Point cur = q.poll();
            if(cur.node == b) {
                return cur.cnt;
            }
            for(int i = 0; i < g[cur.node].size(); i++) {
                //현재 위치의 노드와 연결 되어있는 노드 중 아직 방문하지 않은 노드를 찾기
                int idx = g[cur.node].get(i);
                if(!checked[idx]) {
                    checked[idx] = true;
                    q.add(new Point(idx, cur.cnt+1));
                }
            }
        }
        return -1;
    }

    static int stoi(String s) {return Integer.parseInt(s);}
}

BFS 와 조합 알고리즘을 사용한 완전탐색 문제이다.

 

이 문제는 크게 3가지로 나눌 수 있다.

 

1. 모든 도시 간의 최단거리 구하기

2. 조합 알고리즘으로 치킨 집 정하기

3. 정해진 치킨 집과 모든 빌딩 간의 왕복거리의 합 구하기

 

풀고나서 다른 분들의 풀이를 보니까 플로이드-와샬 알고리즘이란 것을 사용해 모든 빌딩간의 거리를 구했다는데 나는 이 알고리즘을 배운적이 없어서 그냥 BFS로 모든 빌딩의 거리를 구해주었다. 그래도 주어진 범위가 크지 않아 시간초과는 나지 않았다.

 

치킨 집 2개를 임의로 설정 했으면 모든 빌딩에 대해 빌딩과 첫번 째 치킨집, 두번 째 치킨 집 중 더 가까운 거리*2 를 모두 더해주면 된다. 그 후 min 값을 갱신해주고 주어진 제한조건대로 최솟값이 여러개인 조합이 있다면 바꾸도록 짜주면 된다.