백준 1948 Java

문제

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

알고리즘 설명

문제에서 이미 모든 도로가 일방통행이고 사이클이 없다고 (DAG) 나왔다.
대놓고 위상정렬을 사용하라는 가이드를 준다.

쉽게 풀 줄 알았지만 사람들이 지나는 도로의 수를 카운트 하라는 데서 접근을 잘못했다.
https://www.acmicpc.net/board/view/10168
위 링크에서 질문을 올린 사람과 똑같은 잘못을 했는데

for(auto &y: g[x.t]) {
            if(dist[y.t]<dist[x.t]+y.w) { //거리값이 갱신이 되면,
                dist[y.t]=dist[x.t]+y.w;
                cnt[y.t] = cnt[x.t]+1; //기존에 있던 도로 개수를 갱신합니다.
            } else if(dist[y.t]==dist[x.t]+y.w) { //거리값이 똑같은 게 들어오면
                cnt[y.t] += cnt[x.t]+1; //기존에 있떤 도로 개수에 추가해줍니다.
            }
            if(y.t==e) ans=cnt[y.t]; //도착지니까 더해줍니다.
            if(--in[y.t]==0) q.push(y); //해당 정점의 인디그리가 0이면 큐에 푸쒸
        }

거리 값이 똑같은게 들어올때 기존에 있던 도로 갯수에 그대로 추가를 해줬더니
1->2->3->5
2->4->5
이런 식으로 동일한 거리값으로 돌아올때 부모 노드가 가지고 있던 도로값이
동일할 경우 계산이 안되는걸 확인했다. (위 케이스 경우 5가 답인데 6으로 나옴)

결국 도착 지점에서 시작지점까지 다시 탐색을 하면서 도로 개수를 찾아야 했다.
코딩을 새로 해서 겨우 풀긴 풀었다만..
실전에서 이런 실수를 한다면 한참 헤매거나 방향을 못잡을거 같다.

응용력이 너무 없어서 큰일이다. 문제를 많이 봐야 할 것 같다 ㅜㅜ

구현코드

https://github.com/melong222/SW/blob/master/SW/src/BACKJOON/B1948.java