[자바] 백준 21278 - 호석이 두 마리 치킨 (java)

목차

문제 : boj21278

 

 

필요 알고리즘

• 플로이드 와샬, BFS, 다익스트라 등 최단 거리 알고리즘 아무거나 
  
  • 최단 거리를 구할 수 있는 알고리즘으로 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

생각 과정은 이하와 같다.

 

1. 모든 건물에 대해 모든 쌍에 대한 최단 거리를 알 수 있다고 해보자.

 

2. 그렇다면 N개 중 2개의 건물을 고르기로 확정하고, '1'에서 구한 거리 정보로 '최단 시간의 총합'을 구할 수 있을 것이다.

 

3. 그럼 '1'을 유효한 시간 내에 구할 수 있을까? -> N이 100밖에 안되므로 일단 처음 생각난건 대충 플로이드 와샬 박으면 될 것 같았다. 그래도 O(N^3) 밖에 안된다! 그리고 플로이드 와샬로 되면 BFS나 다익스트라로는 당연히 더 널널하게 된다.

 

4. '2'는 유효한 시간 내에 가능할까? 2개의 건물 확정이 O(N^2)이고, 각각의 경우에 대해 모든 건물까지의 최단 시간의 총합을 구해야 하므로 O(N^3)으로 가능하다.

 

5. 최종적으로 O(N^3 + N^3) = O(N^3)으로 가능하다! 그럼 구현 하자.

 

---

 

참고로 일반적인 플로이드 와샬 코드와 다르게 일정 범위에 대해서만 진행된 부분이 헷갈릴 수 있을 것 같다.

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            map[i][j] = map[j][i] = min(map[i][j], map[i][k] + map[k][j]);
        }
    }
}

어차피 양방향 간선이므로, A에서 B로 가는 최단 거리가 확정되면 B에서 A로 가는 최단 거리도 동일하게 확정되는 셈이다. 그래서 모든 NxN 쌍을 볼 필요 없이 위처럼 보면 된다.

 

---

 

'만약 이러한 건물 조합이 여러 개라면, 건물 번호 중 작은 게 더 작을수록, 작은 번호가 같다면 큰 번호가 더 작을수록 좋은 건물 조합이다.'

 

위의 조건이 까다로워 보일 수도 있는데, 사실 그냥 작은 번호부터 차례대로 2쌍식 골라서 보면 자동으로 해결된다.

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

        ...

        if (min > sum) {	// 이게 만족되면 위 조건도 항상 만족된다.
            min = sum;
            ansA = i;
            ansB = j;
        }

    }
}

 

 

코드 : github

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

import static java.lang.Math.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final int INF = 100007;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] map = initMap(n, m);

        floydWarshall(n, map);

        System.out.println(answer(n, map));
    }

    private int[][] initMap(final int n, int m) throws IOException {
        int[][] map = new int[n][n];
        for (int[] row : map)
            Arrays.fill(row, INF);

        while (m-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;

            map[a][b] = map[b][a] = 1;
        }

        return map;
    }

    private void floydWarshall(final int n, int[][] map) {
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = i+1; j < n; j++) {
                    map[i][j] = map[j][i] = min(map[i][j], map[i][k] + map[k][j]);
                }
            }
        }
    }

    private String answer(final int n, final int[][] map) {
        int min = INF;
        int ansA = 0;
        int ansB = 0;

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

                int sum = 0;
                for (int k = 0; k < n; k++) {
                    if (i == k || j == k) continue;

                    sum += min(map[i][k], map[j][k]);
                }

                if (min > sum) {
                    min = sum;
                    ansA = i;
                    ansB = j;
                }

            }
        }

        return String.format("%d %d %d", ansA+1, ansB+1, min*2);
    }
}