(JAVA) 백준 1939번 : 중량 제한 --- [이진탐색, BFS]

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

1939번: 중량제한

 

 

이진탐색과 BFS가 섞인 문제이다.

 

 

구하려는 값 : 두 공장의 이동중량 최댓값.

 

두 공장의 이동중량 : A공장에서 B공장까지 이동하는데 A공장에서 싣은 무게로 B공장까지 갈 수 있는 무게를 뜻함.

 

 

 

범위가 극도로 넓고,

 

시간 제한이 1초 이며

 

최댓값을 구하라는 뜻은 한 값이 아닌 여러 값이 정답으로 나올 수 있다는 뜻 이기 때문에

 

이진탐색을 사용했다.

 

 

 

 

그럼, 바로 매커니즘으로 넘어가겠다.

 

 

 

 

매커니즘

---

  사전 정의

    -  정렬된 배열 : 이동중량 (1 ~ 다리 중 최대중량)

    -  찾는 이유 : A공장에서 B공장으로 이동하는 경로 중 해당 중량(mid) 값과 비교하기 위해

 

 

  1.  ArrayList[n + 1] 로 Graph 생성 및 입력 값 받기

 

 

  2.  low(left) 를 1로, high(right) 를 다리들 중 최대 중량으로 설정.

 

 

  3.  이진탐색 while문 반복

 

 

  4.  BFS 방식을 통해 poll한 공장에 연결된 접점의 공장들을 Queue에 담아가며, B공장에 도착할 때 까지 반복

  *** 물론, 시작 지점은 A공장이다.

 

 

  5.  4번 방식을 진행하면서 간선(다리)들의 무게 중량과 mid(선택한 이동 가능 중량) 값을 비교한다.

    -> mid 값보다 큰 경우 : 해당 공장을 기준으로 4번 이어서 진행. (다음 경로를 탐색)

    -> mid 값보다 작은 경우 : False. 다리를 건너지 못하므로 해당 경로로 탐색 종료. 그냥 다음 원소를 큐에서 poll한다.

 

 

  6.  목적지 공장(B공장)에 하나라도 도착하거나 하나라도 도착하지 못하면 BFS를 종료한다.

    그 후, 하나라도 도착한 경우 -> 별도로 mid 값 저장해서 최댓값 찾기. 다음에 윗 배열 탐색(low = mid + 1)

            하나라도 도착하지 못한 경우 ->다음에 아래 배열 탐색(high = mid - 1)

 

 

  7.  그래서 B공장에 도착한 것들 중 최댓값을 출력하면 끝.

 

 

 

 

 

참고로, 경로 찾을 때

 

처음에는 Queue에서 poll한 원소를 가지고 방문여부나 B공장 지점 여부를 확인했었다.

 

 

하지만!!

 

 

한 지점의 간선이 10만개가 넘는데, 그 중 하나가 도착 지점이라면?

 

 

10만개를 Queue에 넣은 후, 하나씩 까보면서 찾아야 한다.

 

그렇게 되면 소요 시간도 훨씬 증가할 것이다.

 

 

그렇기 때문에 아래에 적은 것처럼 알고리즘을 개선시켜 시간을 훨씬 줄였다. (앞으로도 써먹어야지)

 

 

  -  poll한 원소의 연결 다리들 중 mid값보다 크면 Queue에 넣기

 

  -  poll 한 원소와 인접한 접점(공장들)들을 넣기 전에 방문 여부를 체크하기

 

  -  poll 한 원소와 인접한 접점(공장들)들을 넣기 전에 목적지 공장(B공장) 여부를 체크하기

 

 

 

 

고생많으셨습니다.

 

감사합니다!

 

 

소스코드

---