[AC] 1939 중량제한

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1939.cpp

이 문제 역시 BFS 문제이다. 뭐 DFS로도 풀릴지는 모르겠다.

문제를 처음에는 다익스트라로 접근하였으나 다익스트라로는 몇가지 문제에서 해결이 난해하여 모두 지워버렸다.

그 후 생각을 해보니 해당 지점마다 몇의 무게가 가능한지 값을 매긴 후 그 값을 초과하는건 전부 그값으로 만들고 새로들어오는 값이 크다면 갱신하는 방식을 쓰면 간단할것 같았다.

어쩌다보니 다시 코드가 다익스트라와 조금 비슷한 구도가 되었는데, 결국은 기존값보다 크면 갱신하고 작으면 무시하면서 현재 w보다 새로운 w가 크면 다 깍아버리는 식으로 진행한다. 어차피 한계를 넘으면 옮길수 없기 때문이다. 

생각보다 너무 오래 해맸다. 거의 2시간은 걸린거 같다. 다익스트라를 어떻게든 살려볼려고 하다 망했다.

과거 교수님이 한번 더러워진 옷은 아무리 빨아도 더럽다고 하며 코드도 그렇다고했는데, 정말 그런거였다. 그냥 새로사는게 깔끔한것이다.