백준 1939 - 중량 제한(자바 - BFS 및 이진탐색)

처음으로 마주친 가중치 값이 들어있는 그래프 탐색 및 이진 탐색 문제

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

1939번: 중량제한

 

처음 이 문제를 풀 때는 마지막으로 입력받은 두 공장 사이에서 서로에게 가는 경로를 모두 리스트로 반환받은 후, 각 리스트의 최소값들을 뽑아내면, 그 중에서 가장 큰 값이 한번에 이동 가능한 최대 중량이 될 것이라고 생각하고 문제를 풀었으나 틀렸음이 확인되었다.

 

이 문제를 풀려면 BFS 방식의 그래프 탐색 알고리즘과 더불어 이진 탐색 까지 사용해야 한다고 하는데

BFS 의 경우 아직 인접 행렬로 구현하는 방식은 잘 모르지만 인접 리스트로 구현하는 방식은 그래도 꽤나 숙달이 되어있었다.

 

그러나 문제는 이진 탐색이었다.

기본적으로 이진 탐색이 어떤 방식으로 알고리즘이 수행되는지는 잘 알고 있었다.

정렬된 배열 또는 리스트를 기준으로 최소값을 start, 최대값을 end 로 설정한 다음, 그 중간값인 middle 을 기준으로 찾고자 하는 값이 큰 지 작은지를 비교하여 찾고자 하는 값을 찾아나가는 탐색 알고리즘이다.

이렇게 기본적인 흐름을 알고있다고 해도 근본적으로 문제 풀이를 할 때 어떤 값들을 기준으로 정렬된 리스트 또는 배열을 만들것이며, 또한 이진 탐색 응용 문제의 경우 start, end 의 범위를 정함에 있어서 단순히 middle 값 보다 큰지 작은지를 비교하는 것이 아니라 문제에서 요구하는 특별한 조건을 두고 비교를 해야 하기 때문에, 아직 이진 탐색 문제 풀이에 숙달되지 않은 나 로서는 이번 문제풀이에 대해서 이진 탐색을 어떻게 활용해야 할 지에 대한 감 조차 제대로 잡지 못했다.(중량을 이용해서 이진 탐색을 한다는 생각 까지는 도달했으나, 결정적으로 middle 값에 대한 비교를 어떤 방식으로 할 지에 대해서 감을 잡지 못한것이 스스로 문제를 풀이하는데 실패한 결정적인 원인이 되었다.) 

 

그렇기에 이번에도 듣고 있던 패스트 캠퍼스의 코딩테스트 문제 해결 강의를 참고 하기로 했다.

 

입력 받은 다리들의 가중치들중 최소 값을 start, 최대 값을 end 로 한 이후, middle 값을 이동하는 화물의 중량으로 취급하고 bfs 탐색을 수행한다.

- 입력받은 다리들의 가중치들 중 최소 값을 start, 최대 값을 end 로 한 이후, middle 값을 이동하는 화물의 중량으로 취급하고 bfs 탐색을 수행한다.

- bfs 탐색에서는 시작점부터 도착점 까지 bfs 탐색을 수행하는데, 다리로 연결되어 있는 섬이 아직 방문하지 않음 섬이고 연결되어 있는 다리의 최대 중량이 middle 값 보다 클 경우 '방문이 필요한 섬' 큐에 해당 섬을 적재해줌과 동시에, 이후의 반복문에서 불필요하게 중복되는 값 들이 '방문이 필요한 섬' 큐에 적재되는 것을 막기 위해 방문 상태 배열

에서 해당 섬의 인덱스 값을 true 로 변환시켜 준다.

(해당 처리를 해주지 않으면 '방문이 필요한 섬' 큐에 불필요하게 중복되는 값들이 많이 들어가게 되어, 결국 백준에서 제출 시 메모리 초과 라는 결과를 반환받게 된다.)

- 입력값으로 넘어온 middle 값 을 중량으로 했을 때 도착지에 무사히 도착하는지만 확인하면 되기 때문에 '방문한 섬' 큐는 불필요다고 판단하여 사용하지 않았다.

 

- Main.java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int startIsland = 0;
	static int endIsland = 0;
	static int nodeCount = 0;
	static HashMap<Integer, List<Node>> hashmap = new HashMap<Integer, List<Node>>();
	public static void main(String[] args) throws IOException {
		// 한번의 이동에서 옮길 수 있는 물품들의 중량의 최대값을 이진 탐색으로 찾는다.
		// 두 공장사이에 갈 수 있는 길 중에서 최소 중량에 해당하는 값과 최대 중량에 해당하는 값을 찾는다.
		// 시작할 때는 최소 중량으로 결과값을 초기화해준다.
		// 최소와 최대값의 사이에 있는 중간값을 기준 중량으로 잡고 해당 중량으로 BFS 을 수행해서 목적지 까지 이동이 가능한지를 확인한다.
		// 만약 가능할 경우 더 큰 중량으로도 되는지 확인하기 위해 중량을 증가시키고, 그렇지 않을 경우 중량을 감소 시킨다.(start, end 조절)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		nodeCount = Integer.parseInt(st.nextToken());
		int edgeCount = Integer.parseInt(st.nextToken());
		
		int min = 0;
		int max = 1;
		
		for(int i = 0; i < edgeCount; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			int mainIsland = Integer.parseInt(st.nextToken());
			int connectIsland = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			
			if(value > max)
				max = value;
			if(value <= min)
				min = value;
			
			if(hashmap.containsKey(mainIsland)) {
				List<Node> list = hashmap.get(mainIsland);
				list.add(new Node(connectIsland, value));
				hashmap.replace(mainIsland, list);
			}
			else {
				List<Node> list = new ArrayList<Node>();
				list.add(new Node(connectIsland, value));
				hashmap.put(mainIsland, list);
			}
			
			if(hashmap.containsKey(connectIsland)) {
				List<Node> list = hashmap.get(connectIsland);
				list.add(new Node(mainIsland, value));
				hashmap.replace(connectIsland, list);
			}
			else {
				List<Node> list = new ArrayList<Node>();
				list.add(new Node(mainIsland, value));
				hashmap.put(connectIsland, list);
			}
		}
		
		st = new StringTokenizer(br.readLine(), " ");
		startIsland = Integer.parseInt(st.nextToken());
		endIsland = Integer.parseInt(st.nextToken());
		
	
		int start = min;
		int end = max;
		int middle = 0;
		
		// middle 값을 bfs 메소드에 넘겨서, 해당 값이 목적지 까지 도착할 수 있는지를 확인한다.
		// 목적지 까지 도달한 경우 true, 그렇지 않을 경우 false 를 반환시킨다.
		// 이진 탐색
		int result = start;
		while(start <= end) {
			middle = (start + end) / 2;
			if(bfs(middle)) {
				result = middle;
				start = middle + 1;
			}
			else{
				end = middle - 1;
			}
		}
		
		bw.write(result + "\n");
		bw.flush();
		bw.close();
	}
	private static boolean bfs(int middle) {
		Queue<Integer> needVisit = new LinkedList<Integer>();
		boolean[] visitCheck = new boolean[nodeCount+1];
		
		int island = startIsland;
		needVisit.offer(island);
		
		while(!needVisit.isEmpty()) {
			island = needVisit.poll();
			
			// 도착점이 발견될 경우 즉시 리턴(시간 초과 해결)
			if(island == endIsland)
				return true;
			
			List<Node> islandList = hashmap.get(island);
			if(islandList != null) {
				for(int i = 0; i < islandList.size(); i++) {
					Node node = islandList.get(i);
					if(!visitCheck[node.getConnectIsland()] && node.getValue() >= middle) {
						// needVisit 큐에 너무 많은 값이 들어가는 경우를 방지하기 위해
						// 연결된 섬들을 모두 방문 체크해준다.(메모리 초과 해결)
						visitCheck[node.getConnectIsland()] = true;
						needVisit.offer(node.getConnectIsland());
					}
				}
			}
			
		}
		// 반복문을 무사히 빠져나왔다면 도착점에 도착하지 못했다는 의미
		return visitCheck[endIsland];
	}
}

class Node{
	
	private int connectIsland;
	private int value;
	
	public Node(int connectIsland, int value) {
		this.connectIsland = connectIsland;
		this.value = value;
	}
	
	public int getConnectIsland() {
		return connectIsland;
	}
	public int getValue() {
		return value;
	}
}

- 그래프 상의 가중치를 효과적으로 표현하기 위해 Node 객체를 만들었다.

- bfs 탐색 메소드에서 입력 받은 middle 값을 중량으로 화물이 이동한다고 했을 때, 목적지에 잘 도착했을 경우 true 를 반환하고, 그렇지 않을 경우 false 를 반환한다.

- 목적지에 도착하지 못했을 경우 입력 받은 중량값이 경로상의 다리가 부담 가능한 최대 중량을 초과했다는 뜻이므로, end 의 범위를 middle - 1 로 줄여서 middle 값을 다시 구한 후 bfs 탐색을 수행한다.

- 목적지에 무사히 도착했더라도 결국 가능한 최대 중량을 찾아야 하기 때문에 일단 결과 변수에 해당 middle 값을 저장해둔 후 start 를 middle + 1 로 늘려서 middle 값을 다시 구한 후 bfs 탐색을 수행한다.

- 반복문이 끝나면 결과적으로 결과 변수엔 한번에 이동 가능한 최대 중량 값이 적재되게 된다.