[백준_21278번] 호석이 두 마리 치킨

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

21278번: 호석이 두 마리 치킨

[문제]

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

 이번에 키친 도시로 분점을 확보하게 된 호석이 두마리 치킨은 도시 안에 2개의 매장을 지으려고 한다. 도시는 N 개의 건물과 M 개의 도로로 이루어져 있다. 건물은 1번부터 N번의 번호를 가지고 있다. i 번째 도로는 서로 다른 두 건물 Ai 번과 Bi 번 사이를 1 시간에 양방향으로 이동할 수 있는 도로이다. 키친 도시에서 2개의 건물을 골라서 치킨집을 열려고 한다. 이 때 아무 곳이나 열 순 없어서 모든 건물에서의 접근성의 합을 최소화하려고 한다. 건물 X 의 접근성은 X 에서 가장 가까운 호석이 두마리 치킨집까지 왕복하는 최단 시간이다. 즉, "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 최소화할 수 있는 건물 2개를 골라서 치킨집을 열려고 하는 것이다.

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_21278 {
	static int n,m;
	static final int INF=(int)1e9;
	static int[][] map;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		
		map=new int[n+1][n+1];
		
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				if(i==j)
					continue;
				
				map[i][j]=INF;
			}
		}
		
		// 간선 정보 입력 받기
		for(int i=0;i<m;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			
			map[a][b]=map[b][a]=1;
		}
		
		// 플로이드 와샬 알고리즘
		for(int k=1;k<=n;k++) 
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					map[i][j]=Math.min(map[i][j], map[i][k]+map[k][j]);
	
		int point1=Integer.MAX_VALUE;
		int point2=Integer.MAX_VALUE;
		int min=Integer.MAX_VALUE;
		
		for(int i=1;i<=n;i++) {
			for(int j=i+1;j<=n;j++) {
				// 2개의 지점을 치킨집으로 선정
				int dis=distance(i,j);
				// 더 작은 값을 찾으면 치킨집 장소와 최솟값 갱신
				if(min>dis) {
					point1=i;
					point2=j;
					min=dis;
				}
			}
		}
		
		// 왕복 거리이기 때문에 min*2 한 값을 출력
		System.out.println(point1+" "+point2+" "+min*2);
	}
	
	/*
	 * 모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합을 구하는 문제이기 때문에
	 * 두 치킨집 중 더 가까운 치킨집까지의 거리를 구해 return 한다. 
	 */
	static int distance(int x, int y) {
		int result=0;
		for(int i=1;i<=n;i++)
			result+=Math.min(map[x][i],map[y][i]);
		
		return result;
	}
}

 

[고찰]

 이번 문제를 처음에 접근할 때 치킨집 두 곳을 선정하는 과정을 백트래킹을 사용했는데 코드가 복잡해져 다른 방법이 없을까 고민했다. 해당 문제가 완전탐색 카테고리에 있는 것에 힌트를 얻어 굳이 백트래킹이 아닌 2중 for문을 사용하여 중복 없이 두 지점을 선택하고, 다른 모든 지점으로부터 두 치킨집 중 가까운 지점까지의 거리를 구하는 방법으로 대체했다. 아직 어떤 문제를 보고 어떤 알고리즘을 사용해야 효율적이겠구나 판단하는 능력은 부족한것 같다. 좀 더 노력해야지.