글 읽기 - 중량제한 문제 질문입니다.

gmldud9605 2년 전 0

먼저 가중치가 가장 큰 간선들을 크루스칼로 구해서 이어준다음에 시작점에서 끝점가지 bfs돌면서 그 간선들 중에 최소값을 출력하게 했는데 이렇게 하면 안되나요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 중량 제한
public class BakJoon1939 {
    static int[] parent;

    static int getParent(int x) {
        if (parent[x] == x) return x;
        return parent[x] = getParent(parent[x]);
    }

    static void unionParent(int a, int b) {
        a = getParent(a);
        b = getParent(b);
        if (a > b) parent[a] = b;
        else parent[b] = a;
    }

    static boolean findParent(int a, int b) {
        a = getParent(a);
        b = getParent(b);
        if (a == b) return true;
        else return false;
    }

    static class Dist {
        int point;
        int weight;

        Dist(int point, int weight) {
            this.point = point;
            this.weight = weight;
        }
    }

    static class Point implements Comparable<Point> {
        int a;
        int b;
        int weight;

        Point(int a, int b, int weight) {
            this.a = a;
            this.b = b;
            this.weight = weight;
        }

        @Override
        public int compareTo(Point o) {
            return o.weight - weight;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        // 부모 설정
        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        ArrayList<Dist>[] list = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }
        // 가중치가 큰 순서대로 이어주자
        PriorityQueue<Point> queue = new PriorityQueue<>();
        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 weight = Integer.parseInt(st.nextToken());
            queue.add(new Point(a, b, weight));
        }
        while (!queue.isEmpty()) {
            Point check = queue.poll();
            if (!findParent(check.a, check.b)) {
                unionParent(check.a, check.b);
                //System.out.println(check.weight);
                list[check.a].add(new Dist(check.b, check.weight));
                list[check.b].add(new Dist(check.a, check.weight));
            }
        }

        boolean[] visit = new boolean[N + 1];
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        System.out.println(bfs(list, start, end, visit));
    }

    static int bfs(ArrayList<Dist>[] list, int start, int end, boolean[] visit) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visit[start] = true;
        int minWeight = Integer.MAX_VALUE;
        while (!queue.isEmpty()) {
            int check = queue.poll();
            if (check == end) {
                break;
            }
            for (Dist next : list[check]) {
                if (!visit[next.point]) {
                    visit[next.point] = true;
                    queue.add(next.point);
                    minWeight = Math.min(minWeight, next.weight);
                }
            }
        }
        return minWeight;
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

중량제한 문제 질문입니다.

gmldud9605 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말