백준 1939. 중량제한

 

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

1939번: 중량제한

 

다리들의 관계를 vector<pair<int,int>>>bridge[10001] 에 저장해 줬다.

bridge[a] = pair(b, c) 라면 a 섬과 b섬 사이의 다리의 중량제한이 c다. 

양방향이므로 a,b,c가 주어질때 a에서 b와 b에서 a 두 경우 모두 c로 저장해줘야 한다.

 

left = 0, right는 모든 다리들의 중량중 최댓값으로 하고 이분탐색한다.

mid가 되는 중량에 대하여 하나의 공장에서 다른 공장으로 이동할수 있는지 탐색하면 되는데

처음에 dfs로 했다가 시간초과를 받아서 bfs 로 풀어 정답 처리 받았다.

시간을 줄이기 위해 두번째 공장에 도착하면 바로 true를 리턴해줘야 한다.

 

 

---

2023.03.19 

 

다시 풀어봤다.

이 문제는 그냥 처음에 봤을때는 dfs나 bfs 돌려서 시작지점 부터 도착지점까지 물건을 옮겼을때 가장 중량이 큰 물건을 구하면 될것같다.

하지만 문제는, 문제에서 두 노드 사이에 중복된 경로가 주어질수 있다고 명시되어 있기 때문에, 하나의 노드에서 다른 노드로 이동할때 가중치가 가장 큰 경로를 선택해서 이동해야 한다.

 

여기서 문제가 발생하는데 이렇게 되면 다음 노드로 이동할때마다 가중치가 가장 큰 경로를 탐색해야 한다.

2차원 배열로 최대 가중치 값을 미리 저장해 놓는다고 해도, 10000*10000*sizeof(int) = 4억 byte = 400mb 로 메모리가 초과된다.

 

나는 일단 입력을 모두 받은 후에, 하나의 노드에서 다른 노드로 가는 경로들 중 최댓값만을 선별해서 다시 저장해줬다.

 

그 후에는 bfs 돌리면 된다.