[백준] 21278 호석이 두 마리 치킨 java
문제
컴공 출신은 치킨집을 하게 되어있다. 현실을 부정하지 말고 받아들이면 마음이 편하다. 결국 호석이도 2050년에는 치킨집을 하고 있다. 치킨집 이름은 "호석이 두마리 치킨"이다.
이번에 키친 도시로 분점을 확보하게 된 호석이 두마리 치킨은 도시 안에 2개의 매장을 지으려고 한다. 도시는 N 개의 건물과 M 개의 도로로 이루어져 있다. 건물은 1번부터 N번의 번호를 가지고 있다. i 번째 도로는 서로 다른 두 건물 Ai 번과 Bi 번 사이를 1 시간에 양방향으로 이동할 수 있는 도로이다.
키친 도시에서 2개의 건물을 골라서 치킨집을 열려고 한다. 이 때 아무 곳이나 열 순 없어서 모든 건물에서의 접근성의 합을 최소화하려고 한다. 건물 X 의 접근성은 X 에서 가장 가까운 호석이 두마리 치킨집까지 왕복하는 최단 시간이다. 즉, "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 최소화할 수 있는 건물 2개를 골라서 치킨집을 열려고 하는 것이다.
컴공을 졸업한 지 30년이 넘어가는 호석이는 이제 코딩으로 이 문제를 해결할 줄 모른다. 알고리즘 퇴물 호석이를 위해서 최적의 위치가 될 수 있는 건물 2개의 번호와 그 때의 "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 출력하자. 만약 이러한 건물 조합이 여러 개라면, 건물 번호 중 작은 게 더 작을수록, 작은 번호가 같다면 큰 번호가 더 작을수록 좋은 건물 조합이다.
입력
첫 번째 줄에 건물의 개수 N과 도로의 개수 M 이 주어진다. 이어서 M 개의 줄에 걸쳐서 도로의 정보 Ai , Bi 가 공백으로 나뉘어서 주어진다. 같은 도로가 중복되어 주어지는 경우는 없다. 어떤 두 건물을 잡아도 도로를 따라서 오고 가는 방법이 존재함이 보장된다.
출력
한 줄에 건물 2개가 지어질 건물 번호를 오름차순으로 출력하고, 그때 모든 도시에서의 왕복 시간의 합을 출력한다.
만약 건물 조합이 다양하게 가능하면, 작은 번호가 더 작은 것을, 작은 번호가 같다면 큰 번호가 더 작은 걸 출력한다.
제한
- 2 ≤ N ≤ 100
- N-1 ≤ M ≤ N×(N - 1)/2
- 1 ≤ Ai , Bi ≤ N (Ai ≠ Bi)
풀이
import java.io.*;
import java.util.*;
class Point {
int node;
int cnt;
Point(int node, int cnt) {
this.node = node;
this.cnt = cnt;
}
}
public class Main {
static BufferedReader br;
static StringTokenizer st;
static int n, m, p1, p2, min;
static ArrayList<Integer>[] g;
static int[][] dist;
static int[] picked;
static boolean[] visited;
public static void main(String[] args) throws IOException {
init();
getDist();
solve(0, 1);
System.out.println(p1 + " " + p2 + " " + min);
}
static void init() throws IOException {
min = Integer.MAX_VALUE;
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
n = stoi(st.nextToken());
m = stoi(st.nextToken());
dist = new int[n+1][n+1];
g = new ArrayList[n+1];
visited = new boolean[n+1];
picked = new int[2];
for(int i = 1; i <= n; i++) {
g[i] = new ArrayList<>();
}
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = stoi(st.nextToken());
int b = stoi(st.nextToken());
g[a].add(b);
g[b].add(a);
}
}
static void solve(int cnt, int start) {
if(cnt == 2) {
int sum = 0;
//세운 치킨 집 마다 모든 건물의 거리 구하기
for(int i = 1; i <= n; i++) {
sum += Math.min(dist[picked[0]][i], dist[picked[1]][i])*2;
}
if(min == sum) {
if(p1 == picked[0]) {
if(p2 > picked[1]) {
p1 = picked[0];
p2 = picked[1];
}
} else if(p1 > picked[0]) {
p1 = picked[0];
p2 = picked[1];
}
} else if(min > sum) {
min = sum;
p1 = picked[0];
p2 = picked[1];
}
return;
}
for(int i = start; i <= n; i++) {
picked[cnt] = i;
solve(cnt+1, i+1);
}
}
static void getDist() {
boolean[][] checked = new boolean[n+1][n+1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i == j) {
dist[i][j] = 0;
checked[i][j] = true;
continue;
}
if(!checked[i][j]) {
dist[i][j] = bfs(i,j);
dist[j][i] = dist[i][j];
checked[i][j] = true;
checked[j][i] = true;
}
}
}
}
static int bfs(int a, int b) {
boolean[] checked = new boolean[n+1];
Queue<Point> q = new LinkedList<>();
q.add(new Point(a, 0));
checked[a] = true;
while(!q.isEmpty()) {
Point cur = q.poll();
if(cur.node == b) {
return cur.cnt;
}
for(int i = 0; i < g[cur.node].size(); i++) {
//현재 위치의 노드와 연결 되어있는 노드 중 아직 방문하지 않은 노드를 찾기
int idx = g[cur.node].get(i);
if(!checked[idx]) {
checked[idx] = true;
q.add(new Point(idx, cur.cnt+1));
}
}
}
return -1;
}
static int stoi(String s) {return Integer.parseInt(s);}
}BFS 와 조합 알고리즘을 사용한 완전탐색 문제이다.
이 문제는 크게 3가지로 나눌 수 있다.
1. 모든 도시 간의 최단거리 구하기
2. 조합 알고리즘으로 치킨 집 정하기
3. 정해진 치킨 집과 모든 빌딩 간의 왕복거리의 합 구하기
풀고나서 다른 분들의 풀이를 보니까 플로이드-와샬 알고리즘이란 것을 사용해 모든 빌딩간의 거리를 구했다는데 나는 이 알고리즘을 배운적이 없어서 그냥 BFS로 모든 빌딩의 거리를 구해주었다. 그래도 주어진 범위가 크지 않아 시간초과는 나지 않았다.
치킨 집 2개를 임의로 설정 했으면 모든 빌딩에 대해 빌딩과 첫번 째 치킨집, 두번 째 치킨 집 중 더 가까운 거리*2 를 모두 더해주면 된다. 그 후 min 값을 갱신해주고 주어진 제한조건대로 최솟값이 여러개인 조합이 있다면 바꾸도록 짜주면 된다.