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

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

21278번: 호석이 두 마리 치킨

 

 

🤔 초기 문제 접근

초기에 이 문제를 완전탐색으로 풀고자 했다.

전체 건물들 중에서 두개의 건물을 치킨집으로 선택한 뒤

다른 모든 건물들에서 깊이 우선 탐색을 진행하여 치킨 건물로의 최소 거리를 구하고자 했다.

하지만 전체 19개의 테스트 케이스 중 5개 밖에 맞히지 못했다. 

또한 위와같은 풀이법으로 접근하고자 했다면 다른 건물들이 아닌 치킨 건물에서

다른 건물로의 최소 거리를 구하는게 더 좋았을 것 같다. 

 

🚨풀이에 실패한 코드 (5/19)

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

public class Main {
	static ArrayList<Integer>[] map;
	static boolean[] visit;
	static int[] cost;
	static int n,m;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		map = new ArrayList[n+1];
		visit = new boolean[n+1];
		cost = new int[n+1];
		
		for(int i = 1; i<=n; i++) {
			cost[i] = Integer.MAX_VALUE;
		}
		
		for(int i = 1; i<=n; i++) {
			map[i] = new ArrayList<>();
		}
		
		// 양방향 건물 도로 정보 저장
		for(int i = 0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			map[a].add(b);
			map[b].add(a);
		}
		int c1, c2;
		PriorityQueue<info> pq = new PriorityQueue<>();
		// 임의의 두 건물을 치킨집으로 지정
		for(int i = 1; i<n; i++) {
			for(int j = i+1; j<=n; j++) {
				c1 = i; c2 = j;
				int sum = 0;
				for(int k = 1; k<=n; k++) {
					if(k == c1 || k == c2)
						continue;
					solve(c1, c2, k, k, 0);
					sum += cost[k];
				}
				pq.offer(new info(c1, c2, sum * 2));
			}
		}
		StringBuilder sb = new StringBuilder();
		info answer = pq.poll();
		sb.append(answer.c1).append(" ").append(answer.c2).append(" ").append(answer.w);
		System.out.println(sb);
	}
	public static void solve(int c1, int c2, int start, int cur, int c) {
		// 치킨집 둘중 하나에 도착했을 때
		if(cur == c1 || cur == c2) {
			// 지금까지 걸린 비용을 갱신
			cost[start] = Math.min(cost[start], c);
			return;
		}
		
		visit[cur] = true;
		for(int i = 1; i<=n; i++) {
			if(!visit[i])
				solve(c1, c2, start, i, c+1);
		}

	}
}
class info implements Comparable<info>{
	int c1;
	int c2;
	int w;
	info(int c1, int c2, int w){
		this.c1 = c1;
		this.c2 = c2;
		this.w = w;
	}
	public int compareTo(info i) {
		return this.c2 - i.c2;
	}
}

 

 

풀이에 실패하고 찾아본 결과 플로이드 워셜 알고리즘을 사용하면 간단하게 풀 수 있었다.

플로이드 워셜 알고리즘은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는데 사용되는 알고리즘으로

초기, 모든 거리를 최대값으로 초기화한 후 플로이드 워셜 알고리즘을 사용하여 각 노드 사이의 최단 경로를 구한 뒤

비용이 최소이며 i, j 가 최소인 값을 구하면 된다.

 

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();
    }


}