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

Java

21278 번 - 호석이 두 마리 치킨

문제

접근 방법

주어진 최대 치킨 집 수가 100개이므로, 100개 중 2개의 치킨집을 뽑는다 : 100C2

모든 노드에서 다른 노드까지 가는 최소의 거리를 구해야 하므로, 플로이드 워셜을 사용한다.

이후 조합을 통해 2개의 치킨집을 선택하고 나머지 집에서 치킨 집까지 거리를 구해, 그 거리가 최소가 되는 치킨 집과 거리를 구한다.

코드

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

public class Main {
	static int MAX_VALUE = 987654321;
	static int n, m, result = Integer.MAX_VALUE;
	static int[][] graph;
	static int[] sel;	// 선택 된 치킨집
	static boolean[] vis;	// 방문 여부
	static int r1, r2;	// 결과를 담는 값
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("res/mainInput.txt"));	//제출 할 때 주석해야함
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	
    	graph = new int[n + 1][n + 1];
    	sel = new int[2];
    	
    	for(int i = 1; i <= n; i++) {
    		Arrays.fill(graph[i], MAX_VALUE);
    		graph[i][i] = 0;
    	}
    	
    	int a,b;
    	for(int i = 0; i < m; i++) {
    		stk = new StringTokenizer(br.readLine());
    		a = stoi(stk.nextToken());
    		b = stoi(stk.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;
    			// 끝 노드
    			for(int k = 1; k <= n; k++) {
    				if(graph[j][k] > graph[j][i] + graph[i][k])
    					graph[j][k] = graph[j][i] + graph[i][k];
    			}
    		}
    	}
    	
    	DFS(0,1);
    	
    	
    	System.out.println(r1 + " " + r2 + " " + result * 2);
    	br.close();
	}
	
	// 치킨 집 2개를 뽑는다.
	private static void DFS(int lv, int st) {
		if(lv == 2) {			
		
			int sum = 0;
			
			for(int i = 1; i <= n; i++) {
				if(sel[0] != i && sel[1] != i) {
					int num = Math.min(graph[i][sel[0]], graph[i][sel[1]]);
					sum += num;
				}
			}
			
			if(result > sum) {
				result = sum;
				r1 = sel[0];
				r2 = sel[1];
			}
			
			return;
		}
		for(int i = st; i <= n; i++) {
			sel[lv] = i;
			DFS(lv + 1, i + 1);
		}
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점