[JAVA] 백준 MST 뿌수기 2

 

 

이전 글

https://fladi.tistory.com/422

[JAVA] 백준 MST 뿌수기 1

 

 

백준 MST 뿌수기 시즌2다! 골드3까지는 크루스칼만 잘 쓰면 어느정도 풀리는 것 같아 골드2, 골드1 위주로 풀어보려고 한다. 

 

 

 

 

1368 물대기 - 골드2

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

1368번: 물대기

• 다익스트라라고 생각했는데, 생각해보니 그냥 연결되지 않는 점을 포함해서 mst를 굴리면 될 것 같았다
• 그래서 물을 붓는 경우를 포함해서 프림알고리즘을 사용했더니 맞았다
• 크루스칼은 풀이가 딱히 떠오르지 않아서 못했다

 

프림 코드

class Node implements Comparable<Node> {
    int end;
    int cost;

    public Node(int end, int cost) {
        this.end = end;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.cost, o.cost);
    }
}

public class Main {
    static List<Node>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());

        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] minCost = new int[cnt];

        for (int i =0; i<cnt; i++) {
            int cost = Integer.parseInt(br.readLine());
            pq.add(new Node(i, cost));
        }

        list = new ArrayList[cnt];
        for (int i =0; i<list.length; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i =0; i<cnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j =0; j<i; j++) {
                int cost = Integer.parseInt(st.nextToken());
                list[i].add(new Node(j, cost));
                list[j].add(new Node(i, cost));
            }
        }

        int sum =0;
        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            if (minCost[currentNode.end] != 0) {
                continue;
            }

            minCost[currentNode.end] = currentNode.cost;
            sum += currentNode.cost;

            for (Node near: list[currentNode.end]) {
                if (minCost[near.end] == 0) {
                    pq.add(new Node(near.end, near.cost));
                }
            }
        }
        System.out.println(sum);
    }
}

 

• +) 다른 크루스칼 풀이를 찾아보니 임의의 0 인덱스 지점을 만들어서 물을 붓는경우를 0과 연결해주고, 이를 union find의 기준으로 삼았다. 진짜 참신한 풀이같다. 

 

 

 

10423 전기가 부족해 - 골드2

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

10423번: 전기가 부족해

• 끊어져있지만 최소 신장트리를 구해야하는 건 맞다
• 이전에 존재하지 않는 0번 노드를 만들어서 모두를 연결하는 식으로 크루스칼을 구현해보려고 한다
• 전체적인 코드는 크루스칼과 다를 게 없고, 간선 수는 n개를 뽑는 식으로 구현해보겠다!

 

public class Main {
    static int[] parent;
    static int[][] lines;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st =new StringTokenizer(br.readLine());
        int cityCnt = Integer.parseInt(st.nextToken());
        int cableCnt = Integer.parseInt(st.nextToken());
        int balCnt = Integer.parseInt(st.nextToken());

        parent = new int[cityCnt+1]; //0번은 임의
        for (int i=1; i<parent.length; i++) {
            parent[i] = i;
        }

        lines = new int[cableCnt][3];

        st = new StringTokenizer(br.readLine());
        for (int i =0; i<balCnt; i++) {
            //발전소는 바로 0과 연결 -> visit 처리
            int num = Integer.parseInt(st.nextToken());
            parent[num] = 0;
        }

        for (int i =0; i<cableCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int city1 = Integer.parseInt(st.nextToken());
            int city2 = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            lines[i] = new int[]{city1, city2, cost};
        }

        Arrays.sort(lines, (o1, o2) -> Integer.compare(o1[2], o2[2]));

        long totalCost = 0;
        int cnt = cityCnt - balCnt; //남은 간선 개수
        for (int i =0; i<lines.length; i++) {
            if (cnt == 0) {
                break;
            }

            boolean canConnect = union(lines[i][0], lines[i][1]);
            if (!canConnect) {
                continue;
            }

            totalCost += lines[i][2];
            cnt--;
        }

        System.out.println(totalCost);
    }

    private static boolean union(int city1, int city2) {
        if (city2 == city1)
            return false;

        int parent1= find(city1);
        int parent2= find(city2);
        if (parent1 == parent2) {
            return false;
        }

        if (parent1 < parent2) {
            parent[parent2] = parent1;
        } else {
            parent[parent1] = parent2;
        }

        return true;
    }

    private static int find(int x) {
        if (parent[x] == x)
            return x;

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

• 문제에서 도시의 번호가 1부터 시작하니까 임의의 점은 0으로 지정해주면 된다
• 발전소는 모두 방문처리(parent[i] = 0)해주고
• 나머지 도시들을 모두 연결할 때까지 크루스칼 해준다

 

 

 

20010 악덕 영주 혜유 - 골드2

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

20010번: 악덕 영주 혜유

• mst를 구한 후 트리의 최대거리를 구하듯이 구하면 되겠다

 

class Main {
    static List<int[]>[] arr;
    static int[] parent;
    static long max = -1;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int nodeCnt = Integer.parseInt(st.nextToken());
        int lineCnt = Integer.parseInt(st.nextToken());

        arr = new ArrayList[nodeCnt];
        for (int i =0; i<arr.length; i++)
            arr[i] = new ArrayList<>();

        parent = new int[nodeCnt];
        for (int i =1; i<parent.length; i++)
            parent[i] = i;

        PriorityQueue<int[]> lines = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[2], o2[2]));

        for (int i =0; i<lineCnt; i++) {
            st = new StringTokenizer(br.readLine());
            lines.add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
        }

        long totalCost = 0;
        int cnt = nodeCnt-1;
        while (cnt != 0) {
            int[] tmp = lines.poll();
            boolean canConnect = union(tmp[0], tmp[1]);

            if (!canConnect)
                continue;

            cnt--;
            totalCost += tmp[2];
            arr[tmp[0]].add(new int[]{tmp[1], tmp[2]});
            arr[tmp[1]].add(new int[]{tmp[0], tmp[2]});
        }

        for (int i =0; i<nodeCnt; i++) {
            if (arr[i].size() == 1)
                dfs(i, i, 0);
        }

        System.out.println(totalCost);
        System.out.println(max);
    }

    private static void dfs(int x, int parent, long sum) {
        boolean isLeaf = true;

        for (int[] near: arr[x]) {
            if (near[0] == parent)
                continue;

            isLeaf = false;
            dfs(near[0], x, sum + near[1]);
        }

        if (isLeaf) {
            if (max < sum)
                max = sum;
        }
    }
    private static boolean union(int x, int y) {
        if ( x == y)
            return false;

        int parentX = find(x);
        int parentY = find(y);

        if (parentX == parentY)
            return false;

        if (parentX < parentY)
            parent[parentY] = parentX;
        else
            parent[parentX] = parentY;

        return true;
    }

    private static int find(int x) {
        if (parent[x] == x)
            return x;

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

 

 

 

1944 복제 로봇 - 골드1

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

1944번: 복제 로봇

• 문제를 잘못읽어서 구글링을 통해 풀이를 찾아봤다
• 그냥 bfs를 통해 나와 연결된 간선들을 찾고 크루스칼 해주면 쉽게 풀리는 문제였다

 

class Location {
    int x, y, count;

    public Location(int x, int y, int count) {
        this.x = x;
        this.y = y;
        this.count = count;
    }
}

public class Main {
    static final int[] rowStep = {0, 1, 0, -1};
    static final int[] colStep = {1, 0, -1, 0};
    static ArrayList<Location> list;
    static char[][] arr;
    static PriorityQueue<int[]> pq;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int size = Integer.parseInt(st.nextToken());
        int keyCnt = Integer.parseInt(st.nextToken());

        arr = new char[size][size];
        list = new ArrayList<>();


        for(int i = 0; i < size; i++) {
            String input = br.readLine();
            for(int j = 0; j < size; j++) {
                char c = input.charAt(j);
                arr[i][j] = c;
                if(c == 'S' || c == 'K')
                    list.add(new Location(i, j, 0));
            }
        }

        parent = new int[list.size()];
        for(int i = 1; i < parent.length; i++)
            parent[i] = i;

        pq = new PriorityQueue<int[]>((o1, o2) -> Integer.compare(o1[2], o2[2]));
        for(int i = 0; i < list.size(); i++)
            bfs(i);

        int cost = 0;
        int edge_count = 0;
        while(!pq.isEmpty()) {
            int[] current = pq.poll();
            boolean canConnect = union(current[0], current[1]);

            if (! canConnect)
                continue;

            cost += current[2];
            edge_count++;
        }

        if (edge_count != keyCnt) {
            System.out.println(-1);
        } else {
            System.out.println(cost);
        }
    }

    public static void bfs(int num) {
        Queue<Location> queue = new LinkedList<>();
        boolean[][] visited = new boolean[arr.length][arr[0].length];

        queue.add(list.get(num));
        visited[list.get(num).x][list.get(num).y] = true;
        int cnt = list.size()-1;

        while(!queue.isEmpty()) {
            Location current = queue.poll();
            if (cnt ==0)
                break;

            for(int i = 0; i < 4; i++) {
                int tmpRow = current.x + rowStep[i];
                int tmpCol = current.y + colStep[i];

                if(!isValidLocation(tmpRow, tmpCol))
                    continue;

                if(arr[tmpRow][tmpCol] == '1' || visited[tmpRow][tmpCol])
                    continue;

                visited[tmpRow][tmpCol] = true;

                if(arr[tmpRow][tmpCol] == 'S' || arr[tmpRow][tmpCol] == 'K') {
                    for(int j = 0; j < list.size(); j++) {
                        if(list.get(j).x == tmpRow && list.get(j).y == tmpCol)
                            pq.offer(new int[]{num, j, current.count + 1});
                            cnt--;
                    }
                }
                queue.add(new Location(tmpRow, tmpCol, current.count + 1));
            }
        }
    }

    private static boolean isValidLocation(int tmpRow, int tmpCol) {
        if (tmpRow < 0 || tmpCol < 0 || tmpRow >= arr.length || tmpCol >= arr[0].length)
            return false;
        return true;
    }

    public static boolean union(int x, int y) {
        if (x == y)
            return false;

        int parentX = find(x);
        int parentY = find(y);

        if (parentX == parentY) {
            return false;
        }

        if (parentX < parentY)
            parent[parentY] = parentX;
        else
            parent[parentX] = parentY;

        return true;
    }

    public static int find(int node) {
        if(parent[node] == node)
            return node;

        parent[node] = find(parent[node]);

        return parent[node];
    }
}

• 어렵지 않다!