[백준] 23743 방탈출 - Java

 

 

 

각각의 방이 노드, 워프가 간선을 의미함은 쉽게 이해할 수 있다.

문제는 비상 탈출구를 어떻게 처리하는가인데..

 

두 가지 방법이 있다.

 

1. 브루트포스 방식으로 비상 탈출구를 설치할 수 있는 모든 경우의 수를 살펴본다.

 

즉, 방의 개수가 3이면 1 / 2 / 3 / 1 2 / 1 3 / 2 3 / 1 2 3 이렇게 뽑을 수 있는 모든 수를 뽑고, 뽑힌 수에 비상 탈출구를 설치한 후 최소 스패닝 트리를 돌린다.

 

크루스칼 알고리즘을 사용하는데, 만들어진 MST가 항상 모든 노드를 순회한다는 보장이 없다.

따라서 만들어진 MST에 대해 bfs를 수행해 모든 노드를 순회할 수 있는지 따로 확인하는 작업이 필요하다.

 

구현도 굉장히 힘든데.. 이렇게 풀면 시간 초과가 발생한다.

 

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int INF = 987654321;
    static int N, M;
    static ArrayList<Edge> list = new ArrayList<>();

    static int[] parent;
    static int[] cost;

    static boolean[] select;

    static int min = INF;

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

        parent = new int[N + 1000];       
        cost = new int[N + 1]; 
        select = new boolean[N + 1];

        st = new StringTokenizer(br.readLine());

        for(int i=1; i<N+1; i++){
            cost[i] = Integer.parseInt(st.nextToken());            
        }        

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            list.add(new Edge(a, b, c));            
        }

        Collections.sort(list);        


        PickNumber(1, 0);

        System.out.println(min);

            
    }

    static int find(int a){
        if(parent[a] == a){
            return a;
        }

        return parent[a] = find(parent[a]);
    }

    static void union(int a, int b){
        a = find(a);
        b = find(b);

        if(a != b){            
            parent[b] = a;
        }
    }

    static boolean sameParent(int a, int b){
        a = find(a);
        b = find(b);

        return a == b;
    }

    static void PickNumber(int idx, int cnt){
        if(cnt >= 1){            

            ArrayList<Integer>[] traverse = new ArrayList[1000];
            for(int i=0; i<1000; i++) traverse[i] = new ArrayList<>();

            boolean[] traverse_visit = new boolean[N + 1];

            int ans = 0;

            for(int i=1; i<N+1; i++){
                parent[i] = i;
            }

            // ArrayList<Edge> list2 = new ArrayList<>();

            // for(Edge k : list){
            //     list2.add(k);
            // }

            int before = -1;

            for(int i=1; i<N+1; i++){
                if(select[i]){         
                    if(before == -1){
                        before = i;
                    }else{
                        union(before, i);
                        before = i;
                    }                      

                    ans += cost[i];
                    // list2.add(new Edge(i + 100, i, cost[i]));                    
                    // union(i + 100, i);

                    traverse_visit[i] = true;
                } 
            }
            

            if(cnt == N){                        
                min = Math.min(min, ans);     
                // System.out.print("predetermined "+ ans + " /");           
            }            
                    
            Collections.sort(list);

            for(int i=1; i<N+1; i++){
                if(select[i]){
                    // System.out.print(i + " ");
                }
            }            
            
            for(int i=0; i<list.size(); i++){
                Edge cur = list.get(i);
    
                int start = find(cur.start);
                int end = find(cur.end);
    
                if(!sameParent(start, end)){
                    ans += cur.weight;

                    // System.out.print("weight : " + cur.weight + " ");
                    // System.out.print("union : " + cur.start + " " + cur.end + " ");
                                        
                    union(cur.start, cur.end);                  

                    traverse[cur.start].add(cur.end);
                    traverse[cur.end].add(cur.start);
                    
                    // traverse_visit[start] = true;
                    // traverse_visit[end] = true;
                }                    
            }

            boolean flag = false;

            int start = 0;

            for(int i=1; i<N+1; i++){
                if(!traverse_visit[i]){
                    start = i;
                    Queue<Integer> q = new LinkedList<>();
                    boolean[] visit = new boolean[N + 1];
                    q.add(start);
                    visit[start] = true;

                    boolean flag2 = false;

                    while(!q.isEmpty()){
                        int cur = q.poll();

                        for(int k : traverse[cur]){
                            if(visit[k]) continue;
                            if(traverse_visit[k]) flag2 = true;
                            visit[k] = true;
                            q.add(k);
                        }
                    }

                    if(!flag2){
                        flag = true;
                    }
                    
                    
                }
            }
            
            

            
            
            if(!flag){
                min = Math.min(min, ans);                                    
                // System.out.println("ans is " + ans);   
            }else{
                // System.out.println("not satisfied");
            }            
            
        }

        for(int i=idx; i<N+1; i++){
            if(select[i]) continue;

            select[i] = true;
            PickNumber(i, cnt + 1);
            select[i] = false;     
        }
        
    }
}

class Edge implements Comparable<Edge>{
    int start, end, weight;

    Edge(int start, int end, int weight){
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    public int compareTo(Edge o2){
        return weight > o2.weight ? 1 : -1;
    }    
}

 

 

 

따라서 다른 방법을 생각해야 한다.

 

 

2. 가상 노드 연결

 

비상 탈출구들을 하나의 노드로 판단하고, 각각의 설치 비용에 따라 간선으로 연결해준다.

이후 크루스칼을 돌리면 고립된 노드도 함께 판단할 수 있다.

 

구현도 간단하고 시간도 빠르다.

 

 

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int INF = 987654321;
    static int N, M;
    static ArrayList<Edge> list = new ArrayList<>();

    static int[] parent;
    static int[] cost;

    static boolean[] select;

    static int min = INF;

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

        parent = new int[N + 1000];       
        cost = new int[N + 1]; 
        select = new boolean[N + 1];

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            list.add(new Edge(a, b, c));            
        }

        st = new StringTokenizer(br.readLine());

        for(int i=1; i<N+1; i++){
            cost[i] = Integer.parseInt(st.nextToken());
            list.add(new Edge(0, i, cost[i]));
        }        

        Collections.sort(list);        

        for(int i=0; i<N+1; i++){
            parent[i] = i;
        }
        int ans = 0;

        for(int i=0; i<list.size(); i++){
            Edge cur = list.get(i);

            int start = find(cur.start);
            int end = find(cur.end);

            if(!sameParent(start, end)){
                ans += cur.weight;
                union(cur.start, cur.end);
            }
        }

        // PickNumber(1, 0);

        System.out.println(ans);

            
    }

    static int find(int a){
        if(parent[a] == a){
            return a;
        }

        return parent[a] = find(parent[a]);
    }

    static void union(int a, int b){
        a = find(a);
        b = find(b);

        if(a != b){            
            parent[b] = a;
        }
    }

    static boolean sameParent(int a, int b){
        a = find(a);
        b = find(b);

        return a == b;
    }

    static void PickNumber(int idx, int cnt){
        if(cnt >= 1){            

            ArrayList<Integer>[] traverse = new ArrayList[1000];
            for(int i=0; i<1000; i++) traverse[i] = new ArrayList<>();

            boolean[] traverse_visit = new boolean[N + 1];

            int ans = 0;

            for(int i=1; i<N+1; i++){
                parent[i] = i;
            }

            // ArrayList<Edge> list2 = new ArrayList<>();

            // for(Edge k : list){
            //     list2.add(k);
            // }

            int before = -1;

            for(int i=1; i<N+1; i++){
                if(select[i]){         
                    if(before == -1){
                        before = i;
                    }else{
                        union(before, i);
                        before = i;
                    }                      

                    ans += cost[i];
                    // list2.add(new Edge(i + 100, i, cost[i]));                    
                    // union(i + 100, i);

                    traverse_visit[i] = true;
                } 
            }
            

            if(cnt == N){                        
                min = Math.min(min, ans);     
                // System.out.print("predetermined "+ ans + " /");           
            }            
                    
            Collections.sort(list);

            for(int i=1; i<N+1; i++){
                if(select[i]){
                    // System.out.print(i + " ");
                }
            }            
            
            for(int i=0; i<list.size(); i++){
                Edge cur = list.get(i);
    
                int start = find(cur.start);
                int end = find(cur.end);
    
                if(!sameParent(start, end)){
                    ans += cur.weight;

                    // System.out.print("weight : " + cur.weight + " ");
                    // System.out.print("union : " + cur.start + " " + cur.end + " ");
                                        
                    union(cur.start, cur.end);                  

                    traverse[cur.start].add(cur.end);
                    traverse[cur.end].add(cur.start);
                    
                    // traverse_visit[start] = true;
                    // traverse_visit[end] = true;
                }                    
            }

            boolean flag = false;

            int start = 0;

            for(int i=1; i<N+1; i++){
                if(!traverse_visit[i]){
                    start = i;
                    Queue<Integer> q = new LinkedList<>();
                    boolean[] visit = new boolean[N + 1];
                    q.add(start);
                    visit[start] = true;

                    boolean flag2 = false;

                    while(!q.isEmpty()){
                        int cur = q.poll();

                        for(int k : traverse[cur]){
                            if(visit[k]) continue;
                            if(traverse_visit[k]) flag2 = true;
                            visit[k] = true;
                            q.add(k);
                        }
                    }

                    if(!flag2){
                        flag = true;
                    }
                    
                    
                }
            }
            
            

            
            
            if(!flag){
                min = Math.min(min, ans);                                    
                // System.out.println("ans is " + ans);   
            }else{
                // System.out.println("not satisfied");
            }            
            
        }

        for(int i=idx; i<N+1; i++){
            if(select[i]) continue;

            select[i] = true;
            PickNumber(i, cnt + 1);
            select[i] = false;     
        }
        
    }
}

class Edge implements Comparable<Edge>{
    int start, end, weight;

    Edge(int start, int end, int weight){
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    public int compareTo(Edge o2){
        // return weight > o2.weight ? 1 : -1;
        if(weight > o2.weight){
            return 1;
        }else if(weight < o2.weight){
            return -1;
        }else{
            return 0;
        }
    }    
}

 

 

(브루트포스 방식의 코드를 조금 수정했다.)