BOJ 13905 세부 주의할 점과 간략 풀이

이 문제는 1939 중량 제한 문제와 거의 같은 문제인데,
주의해야할 점이 있다.
내가 처음에 이분 탐색을 이용해서 구현했는데, WA를 받았다.
내 코드를 아무리 살펴봐도 틀린점이 없어 보이는데... 뭐 틀린점이 없어보여도 틀린 경우가 많긴하지만...
알고보니 난 이분 탐색을 구현할 때, l=0, r=1000000로 두고, 답은 r을 출력하는 식으로 했는데, 그것이 틀린 원인이었다. l=1로 두면 AC를 받는다. 엥?? 뭐지 그래서 이번에는 r을 출력하는 방식이 아닌 ans라는 변수를 따로 두고 했는데 ans를 -1, 1로 초기화해 봤는데 둘 다 틀리게 나오는 것이었다. 그래서 ans를 0으로 초기화했더니 AC를 받았다...!?...

생각해보니... 출발지에서 목적지까지 갈 수 없는 경우가 있는 것 같다.
위에서 l, r을 사용할 경우 l=0으로 두고 할 경우, r=mid-1이 계속 되어 결국 r=-1이 되고 끝나게 된다. 그래서 목적지까지 갈 수 없는 경우는 0을 출력해야 되는데 그렇지 못한 것이다.
하지만 같은 경우에 l=1로 둘 경우, r=0이 되고 끝난다.

분명 이분 탐색으로 모든 경우를 다 볼 수는 있지만, 아예 경로가 존재하지 않는 경우를 전혀 생각못했다.

l, r을 이용해서만 풀려고 했던 것과, ans를 -1로 초기화하는 습관때문에 알아낼 수 있었다.
감사합니다.

다익스트라나 MST+LCA로 풀 경우에도 주의해야 할 것 같다.
다익스트라는 할 만할 것 같은데, 목적지까지 가는 경로가 없는 경우 MST를 만들 때 목적지가 포함이 안될 것이고... 그럼 MST에서 depth를 구할 때 -1로 초기화하고, 출발점이나 도착점의 depth가 제대로 구해지지 않으면 거기서 바로 끊어서 0을 출력하든지 해야할 것 같다.
크루스칼로 MST를 만든 후에 출발점과 도착점이 같은 그래프에 속해있는지를 살펴보고 같은 그래프가 아니면 바로 0을 출력하는 것이 더 좋아보인다.

MST + LCA로 풀었는데, WA를 받았다. 도대체 뭐가 문제인지 모르겠어서 랜덤 데이터로 비교해 보는데도... 계속 정답 코드와 같은 결과가 나오다가.. 결국 다른 데이터를 발견했다!!!
아... 다행히 데이터 크기도 작아서 직접 MST를 그려보고 했는데...
이 문제에서는 경로가 존재하지 않는 경우도 있다고 했는데, 바로 그래프가 여러개로 나눠져 있을 수 있다는 것이고, 정점이 동떨어져 있을 수도 있다.
나는 MST에서 depth를 찾기 위해서 dfs를 할 때, root를 1로 두고 했는데... 1이 MST에 포함 안 되었을 수도 있다. 그래서 안전하게 출발점 or 도착점을 root로 하면 될 것 같다.
AC를 받았다!! 아 진짜 이런 건 생각도 못했다.. 진짜 그래프가 나눠져 있으니 주의해야 할 것이 많은 것 같다. 아마 랜덤 데이터가 나오지 않았다면 못 찾았을 것이다... 감사합니다!

이제 dijkstra, MST+LCA로 풀었으니
MST+dfs로 풀어 봐야겠다.
dfs가 쉬울 줄 알았는데 막상 해보니 까다롭다... 오히려 MST+다익스트라 돌리는 게 더 쉬울지도... dfs로 구현하기가 힘들어서 일단 전역변수 ans를 두고, dfs를 s에서 시작해서 return값은 도달한 노드번호로 해서 return값이 e이면 ans에 해당 cost를 비교해서 최소값을 넣고 return e를 해준다... 그냥 아래에 적어놓은 질문 게시판의 어떤 분의 방법이 젤 좋을 듯하다. MST를 만들면서 찾아주는 게 제일 나을듯... 한 번 그렇게 구현해 봐야겠다.
이 방법이 제일 간단하고 멋지고 빠른 것 같다.

그리고 MST로 할 경우 LCA외에 dfs로 해도 되겠지만, 질문 게시판에 올라온 어떤 분의 글을 보니 그 분은 크루스칼 알고리즘으로 MST를 만들면서 출발점과 도착점이 같은 부모를 가지게 되는 순간(같은 그래프에 속하는 순간)의 간선의 가중치 값을 출력하는 식으로 구현하셨다. 그 순간이 출발점과 도착점 사이를 잇는 경로가 완성되는 순간이면서 그 때의 가중치가 최소값이기 때문이다. 물론 이 경우도 마지막에 0을 출력해줘야 한다.
1939 중량제한 문제도 이렇게 풀어봐야겠다.

이 문제는 데이터로 여러 개로 나눠져 있는 그래프가 들어오기 때문에 고려할 부분이 좀 있는 문제였다. 좋은 문제 였고 많은 공부가 되었다.

참고 : https://www.acmicpc.net/board/view/10880