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

문제 링크

21278번: 호석이 두 마리 치킨

분류

브루트포스 알고리즘, 플로이드–워셜, 그래프 이론, 그래프 탐색, 최단 경로

문제 설명

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

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

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

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

입력

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

출력

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

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

---

문제 요약

N개의 집 중 2개를 선택해서 치킨 집을 열 때, 모든 건물에서 가장 가까운 치킨집까지 왕복 최단 시간의 총합을 구할 수 있는 건물 x, y와 최단 시간의 총합 구하기. 최단 시간의 총합이 동일하다면  건물의 숫자가 작은거 구하기

 

접근

치킨집 2개를 선택했을 때 모든 건물에서 치킨집까지의 최단 거리를 구해야한다. 어떻게 치킨집을 설정할 것이냐?

 

문제에 힌트가 있다. '만약 이러한 건물 조합이 여러 개라면, 건물 번호 중 작은 게 더 작을수록, 작은 번호가 같다면 큰 번호가 더 작을수록 좋은 건물 조합이다.'  건물 조합이 여러 개일 때 우선순위를 정해줬다. 연산 과정에서 건물 조합이 여러개일 수 있고, 그 때 출력해야 되는 값을 알려줬다. 높은 확률로 완전탐색이다!

 

완전탐색을 할 때 시간초과가 나지 않는지 시간을 체크해준다. 치킨집에서 모든 건물간의 최단 거리를 구하기 위해 다익스트라 알고리즘을 이용하기로 했다. 

/*
    100개의 노드 중 2개 고르기 -> 100C2 = 약 4600
    다익스트라 ElogV *2 = 100log4600 X2 = 2400
    => 11,040,000 (약 천만)
 */

 

근데 문제를 보니 가중치가 없는 간선이었다. BFS로 충분할 것 같아서 BFS를 이용하기로 했다. BFS는 시간 복잡도가 O(v+e)로 더욱 널널하다.  

 

알고리즘

1. 치킨집 건물 선택

완전탐색하면 되니 이중포문으로 모든 조합을 다 수행해준다.

	for(int i=1; i<= N-1; i++){
            dis = new int[N+1];
            Arrays.fill(dis, Integer.MAX_VALUE);

            for(int j=i+1; j<=N; j++){
                // i,j 위치에 치킨집을 설치했다고 가정
                dis[i] = dis[j] = 0;
                int temp = BFS(i,j, dis);

                if(disSum > temp){
                    result[0] = i;
                    result[1] = j;
                    disSum = temp;
                }
            }
        }

 

2. BFS 탐색

치킨집으로 설정한 건물들은 `dis`값을 0으로 지정하고 나머지는 `Max`값으로 초기화한다. 2개의 치킨집 건물을 큐에 넣은 후 BFS 탐색을 진행한다. 이때 갱신이 될 떄마다 총합을 나타내는 `sum`변수에 갱신값을 더한다.

public static int BFS(int s1, int s2, int [] dis){
        int sum = 0;
        boolean [] isVisited = new boolean[N+1];
        Queue<Integer> que = new LinkedList<>();

        que.add(s1);
        que.add(s2);
        isVisited[s1] = isVisited[s2] = true;

        while(!que.isEmpty()){
            int cur = que.poll();
            for(int next : graph[cur]){
                if(!isVisited[next]){
                    que.add(next);
                    dis[next] = dis[cur]+1;
                    sum += dis[next];
                    isVisited[next] = true;
                }
            }
        }
        return sum;
    }

 

3. 최소값 비교

`i`, `j` 건물을 치킨집으로 설정했을 때 모든 건물의 촤단거리 총합을 `BFS()` 함수로 알아내 기존의 최소값과 비교한다. 만약 더 작을 시 출력할 수 있도록 따로 변수에 저장한다.

	int temp = BFS(i,j, dis);

                if(disSum > temp){
                    result[0] = i;
                    result[1] = j;
                    disSum = temp;
                }

 

전체코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

/*
    100개의 노드 중 2개 고르기 -> 100C2 = 약 4600
    다익스트라 ElogV *2 = 100log4600 X2 = 2400
    => 11,040,000 약 천만
 */
public class Main {

    public static int disSum = Integer.MAX_VALUE;
    public static int[] result = new int[2];
    public static int N, M;
    public static ArrayList<Integer>[] graph;
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N+1];
        for(int i=0; i< graph.length; i++){
            graph[i] = new ArrayList<>();
        }

        // 간선 정보 입력받기
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            graph[v1].add(v2);
            graph[v2].add(v1);
        }

        int [] dis;
        for(int i=1; i<= N-1; i++){
            dis = new int[N+1];
            Arrays.fill(dis, Integer.MAX_VALUE);

            for(int j=i+1; j<=N; j++){
                // i,j 위치에 치킨집을 설치했다고 가정
                dis[i] = dis[j] = 0;
                int temp = BFS(i,j, dis);

                if(disSum > temp){
                    result[0] = i;
                    result[1] = j;
                    disSum = temp;
                }
            }
        }
        bw.write(result[0]+" " + result[1]+" ");
        bw.write(disSum*2 + "");
        bw.flush();
    }

    public static int BFS(int s1, int s2, int [] dis){
        int sum = 0;
        boolean [] isVisited = new boolean[N+1];
        Queue<Integer> que = new LinkedList<>();

        que.add(s1);
        que.add(s2);
        isVisited[s1] = isVisited[s2] = true;

        while(!que.isEmpty()){
            int cur = que.poll();
            for(int next : graph[cur]){
                if(!isVisited[next]){
                    que.add(next);
                    dis[next] = dis[cur]+1;
                    sum += dis[next];
                    isVisited[next] = true;
                }
            }
        }
        return sum;
    }

}

 

정답 제출하고 다른 사람들의 걸린 시간을 봤는데 나보다 5배나 빠른 풀이가 존재했었다. 어떻게 그렇게 빠르나 봤더니 `플로이드 워샬` 알고리즘을 이용했다. `플로이드 워샬`로 다시 도전해봤다.

 

플로이드 워셜 - 알고리즘

이 문제에서 필요한 것은 건물 i 에서 j로 가는 최단거리이다. 나는 이를 BFS로 매번 구하였지만, 플로이트 워샬을 통해 한 번에 모두 구한 후 적절히 사용하면 훨씬 시간을 줄일 수 있다. 시간이 반으로 줄었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;


public class Main {

    public static int disSum = Integer.MAX_VALUE;
    public static int[] result = new int[2];
    public static int N, M;
    public static ArrayList<Integer>[] graph;
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 워셜
        int dis[][] = new int[N+1][N+1];

        for(int i=0; i<dis.length; i++){
            Arrays.fill(dis[i], 100001);
            dis[i][i] = 0;
        }

        // 간선 정보 입력받기
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            dis[v1][v2] = 1;
            dis[v2][v1] = 1;
        }

        for(int k=1; k<=N; k++){
            for(int i=1; i<=N; i++){
                for(int j=1; j<=N; j++){
                    dis[i][j] = Math.min(dis[i][k] + dis[k][j], dis[i][j]);
                }
            }
        }
        

        for(int i=1; i<= N-1; i++){
            for(int j=i+1; j<=N; j++){
                int temp = 0;
                for(int k=1; k<=N; k++){
                    temp += Math.min(dis[i][k], dis[j][k]);
                }

                if(disSum > temp){
                    result[0] = i;
                    result[1] = j;
                    disSum = temp;
                }
            }
        }
        bw.write(result[0]+" " + result[1]+" ");
        bw.write(disSum*2 + "");
        bw.flush();
    }


}

 

 

시간 복잡도 계산

`플로이드 워샬`은 삼중 루프를 사용하기 때문에 O(V^3)이지만, 이 문제는 노드의 최대 개수가 100이다. 때문에 총 1,000,000 (백만) 번 수행된다. 그리고 최소값을 알아내기 위해 다시 삼중 루프를 돌아야하므로 전체적으로  2,000,000 (이백만) 걸린다.

1,000,000 (백만)