BOJ - 1939 중량제한

leehyunjon·2022년 6월 27일

BFS boj 이분탐색 크루스칼

Algorithm

목록 보기

85/162

Problem

Solve

해당 문제는 한 번의 이동에서 옮길수 있는 최대 중량을 구하는 문제이다.

주어지는 중량이 최대 10억이므로 중량을 구하는 것에 이분탐색을 고려해봐야한다.

이분탐색으로 할 시 임의 다리가 버틸수 있는 중량을 선택하고 해당 중량으로 BFS를 통해 하나의 공장에서 다른 공장으로 이동가능 여부를 판단한다.

이동이 불가능 하면 중량의 범위를 줄이기 위해 end = mid-1, 이동이 가능하면 중량의 범위를 늘리기 위해 start = mid+1로 범위를 갱신한다.
중량의 범위는 가능한 이동 중량의 최대이기 때문에 start==end 일 때 갱신된 end의 무게를 반환한다.(두 섬을 연결하는 경로는 반드시 존재한다.)

다른 방법으로는 크루스칼 알고리즘을 사용하는 방법이다.

크루스칼 알고리즘은 두 정점의 비용이 적은것 부터 그룹을 생성하고 두 정점을 연결할때 같은 그룹인 경우 사이클이 발생하기 때문에 해당 연결은 무시된다.
위를 반복하게 되면 모든 정점은 사이클 없이 연결되게 된다. 이를 최소 신장 트리라고 한다.

해당 문제에서는 하나의 공장이 있는 정점과 다른 공장이 있는 정점을 연결 하되 최대의 중량을 얻어야 하기 때문에 각 정점이 연결된 비용이 작은 것이 아닌 큰 것부터 각 정점을 연결한다.

//크루스칼
//각 정점의 비용으로 정렬된 리스트에서 비교하려는 두 정점이 같은 그룹이라면 무시하고 
//다른 그룹이라면 그룹화를 실행한다.
static int cruscal() {
		for (int i = 0; i < M; i++) {
			Edge e = pq.poll();

			if (find(e.u) != find(e.v)) {
				union(e.u, e.v);
				if(find(parents[start]) == find(parents[end])){
					return e.cost;
				}
			}
		}
		return -1;
	}

	//그룹화
    //그룹화하려는 두 정점의 그룹을 가져온다.
    //두 그룹 중 값이 작은 그룹에 다른 정점이 그룹에 포함되게 된다.
	static void union(int v1, int v2){
		v1 = find(v1);
		v2 = find(v2);

		if(v1 > v2){
			parents[v1] = v2;
		}else{
			parents[v2] = v1;
		}
	}

	//주어진 정점의 그룹을 찾는다.
    //그룹의 식별자는 해당 그룹에서 가장 작은 정점의 번호를 가리키게된다.
	static int find(int v) {
		if (parents[v] == v)
			return v;
		else
			return find(parents[v]);
	}

Code

이진탐색 + BFS

public class 중량제한_BFS {
	static int N;
	static int M;
	static List<Edge>[] graph;
	static int max;
	static int start;
	static int end;

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

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		//인접 배열시 시간초과 발생
        //인접 리스트 사용
		graph = new List[N + 1];
		for (int i = 1; i <= N; i++) {
			graph[i] = new ArrayList<>();
		}

		max = 0;
		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());

			graph[a].add(new Edge(a, b, c));
			graph[b].add(new Edge(b, a, c));
			max = Math.max(max, c);
		}

		st = new StringTokenizer(br.readLine(), " ");
		start = Integer.parseInt(st.nextToken());
		end = Integer.parseInt(st.nextToken());

		int answer = binarySearch();
		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static int binarySearch(){
		int left = 0;
		int right = max;
		while(left<=right){
			int mid = (left+right)/2;

			if(bfs(mid)){
				left = mid+1;
			}else{
				right = mid-1;
			}
		}
		return right;
	}

	static boolean bfs(int tempCost){
		Queue<Integer> queue = new LinkedList<>();
		boolean[] visit = new boolean[N+1];

		visit[start] = true;
		queue.offer(start);

		while(!queue.isEmpty()){
			int v = queue.poll();
			if(v == end) return true;
			for(Edge e : graph[v]){
            	//방문하지 않고 임시 중량보다 같거나 큰 비용을 가지는 연결만 가능.
				if(!visit[e.v] && e.cost >= tempCost){
					queue.offer(e.v);
					visit[e.v] = true;
				}
			}
		}
		return false;
	}

	static class Edge {
		int u;
		int v;
		int cost;

		public Edge(int u, int v, int cost) {
			this.u = u;
			this.v = v;
			this.cost = cost;
		}
	}
}

크루스칼

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 중량제한 {
	static int N;
	static int M;
	static PriorityQueue<Edge> pq;
	static int[] parents;
	static int start;
	static int end;

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

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		pq = new PriorityQueue<>();
		parents = new int[N + 1];

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

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

			pq.offer(new Edge(a, b, c));
		}

		st = new StringTokenizer(br.readLine(), " ");
		start = Integer.parseInt(st.nextToken());
		end = Integer.parseInt(st.nextToken());

		int answer = cruscal();

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	//크루스칼
	static int cruscal() {
		for (int i = 0; i < M; i++) {
			Edge e = pq.poll();

			if (find(e.u) != find(e.v)) {
				union(e.u, e.v);
				if(find(parents[start]) == find(parents[end])){
					return e.cost;
				}
			}
		}
        //공장이 있는 두 섬은 무조건 연결되기 때문에 필요없는 값.
		return -1;
	}

	//두 정점 그룹화
	static void union(int v1, int v2){
		v1 = find(v1);
		v2 = find(v2);

		if(v1 > v2){
			parents[v1] = v2;
		}else{
			parents[v2] = v1;
		}
	}

	//정점의 그룹 찾기
	static int find(int v) {
		if (parents[v] == v)
			return v;
		else
			return find(parents[v]);
	}

	static class Edge implements Comparable<Edge> {
		int u;
		int v;
		int cost;

		public Edge(int u, int v, int cost) {
			this.u = u;
			this.v = v;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o1) {
			return o1.cost - this.cost;
		}
	}
}