자바(백준) 21278 호석이 두 마리 치킨

오답 노트 & 알게 된 점

문제를 보면 가중치가 1이라고 했으므로 최단 경로를 구하는 알고리즘 중

BFS를 사용하면 된다고 생각했다.

 

문제에서 건물이 2개가 지어지고, N이 최대 100이다.

따라서 시간복잡도는 100C2 * 100 * 100으로 1억이 안된다.

 

즉, N개 중에 2개를 중복X, 순서X인 조합을 구하여,

2개의 노드에서 나머지 노드들 간의 거리를 구하면 된다.

static void dfs(int start, int cnt) {
        if(cnt == 2){
            bfs();
            return;
        }

        for (int i = start; i <= N; i++) {

            select[cnt] = i;
            dfs(i + 1, cnt + 1);
        }
    }

 

여기서 1번 건물, 2번 건물이 있을 때 건물 번호의 숫자가 작을수록 좋다고 했다.

이 점은 조합을 구할 때, 애초부터 작은 건물부터 짓기 때문에 자동으로 조건을 만족시킬 수 있다.

물론, 최소값을 구할 때, 같다라는 조건을 없애야한다!

if(ans > sum){
            ans = sum;
            build1 = select[0];
            build2 = select[1];
        }

 

---

코드

package bfs_dfs;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ21278 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, M;
    static ArrayList<Integer> A[];
    static int select[] = new int[2];
    static int ans = Integer.MAX_VALUE;
    static int build1, build2;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        dfs(1, 0);
 
        ans = ans * 2; //왕복
 
        System.out.println(build1 + " " + build2 + " " + ans);
    }
 
    static void dfs(int start, int cnt) {
        if(cnt == 2){
            bfs();
            return;
        }
 
        for (int i = start; i <= N; i++) {
 
            select[cnt] = i;
            dfs(i + 1, cnt + 1);
        }
    }
 
    private static void bfs() {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(select[0]);
        q.offer(select[1]);
 
        int dist[] = new int[N + 1];
        boolean visit[] = new boolean[N + 1];
        for (int i = 1; i <= N; i++) dist[i] = Integer.MAX_VALUE;
        dist[select[0]] = 0;
        dist[select[1]] = 0;
 
        while (!q.isEmpty()) {
            int x = q.poll();
 
            for (int k : A[x]) {
                if(dist[k] > dist[x] + 1) dist[k] = dist[x] + 1;
                if(visit[k]) continue;
                q.offer(k);
                visit[k] = true;
            }
        }
        int sum = 0;
 
        for (int i = 1; i <= N; i++) {
            sum += dist[i];
        }
 
        //여기서 같다라고 하지 않은 이유는
        //문제에서 건물 번호가 낮을 수록 좋다고 함.
        //어차피 조합에서 건물 낮은 얘들부터 뽑히니까 그런거임
        if(ans > sum){
            ans = sum;
            build1 = select[0];
            build2 = select[1];
        }
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        M = atoi(st.nextToken());
 
        A = new ArrayList[N + 1];
 
        for (int i = 0; i <= N; i++) A[i] = new ArrayList<>();
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = atoi(st.nextToken());
            int e = atoi(st.nextToken());
 
            A[s].add(e);
            A[e].add(s);
        }
    }
}