[BaekJoon] 1939 중량제한 (java)

🔗 문제 링크

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

👨🏻‍💻 작성한 코드

package backjoon;

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

class Node {
	int nodeId; // 연결된 node의 id
	int weight;
	
	public Node(int nodeId, int weight) {
		this.nodeId = nodeId;
		this.weight = weight;
	}
}

public class Main {

	static ArrayList<ArrayList<Node>> list = new ArrayList<>();
	
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		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());
		
		
		int max = 0;
		int min = Integer.MAX_VALUE;
		
		for (int i=0; i<=n; i++) {
			list.add(new ArrayList<Node>());
		}
		
		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.get(a).add(new Node(b,c));
			list.get(b).add(new Node(a,c));
			
			max = Math.max(max, c);
			min = Math.min(min, c);
		}
		
		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		
		int result = 0;
		while (min <= max) {
			int mid = (min + max)/2;
			if (bfs(start, end, n, mid)) {
				result = mid;
				min = mid+1;
			}
			else {
				max = mid -1;
			}
		}
		System.out.println(result);
		
		
	}

	static boolean bfs(int start, int end, int n, int mid) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(start);
		boolean[] visited = new boolean[n + 1];
		visited[start] = true;
		
		while (!queue.isEmpty()) {
			int x = queue.poll();
			if (x == end) return true;
			 
			ArrayList<Node> temp = list.get(x);
			
			for (Node node : temp) {
				if (!visited[node.nodeId] && node.weight >= mid) {
					visited[node.nodeId] = true;
					queue.offer(node.nodeId);
				}
			}
		}
		return false;
	}
}

📝 정리

이번 문제는 BFS와 이진탐색을 이용하여 푸는 문제였다.
사실 이전까지 DFS와 BFS의 돌아가는 구조는 이해하고 있었으나 어떤 상황에 BFS를 사용하고 어떠한 상황에 DFS를 사용해야 하는지 구분을 하기가 힘들었다. 하지만 이번 문제를 접하며 DFS, BFS의 개념들을 다시 공부하며 어떠한 상황에 어떤 알고리즘을 사용해야하는지 구분을 할 수 있게 된것 같다.

ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
DFS - 모든 친구 관계들을 다 살펴보며 탐색한다.
BFS - Ash와 가까운 관계부터 탐색해간다.

이번 문제는 가까운 관계부터 탐색을 하는 BFS가 DFS보다 해당 문제에 사용하기 적합하여 BFS로 구현을 하게 되었다.

코드를 작성하며 많은 시간이 걸렸고 중간에 변수명 오타도 있어서 많은 시간 낭비도 한 것 같다...

문제를 풀며 더욱 성장할 수 있도록 노력해야겠다👍