P1738

[baekjoon-1738] 골목길

풀이 과정

경로를 구하는 법을 잘 모르겠어서 다른 풀이를 참고했다. 다음에 풀 때는 잘 풀 수 있기를 !!

• 가중치가 최대가 되는 경로를 구해야 하므로 주어진 가중치에 -1을 곱하여 최단경로 문제로 바꿀 수 있다.
• 경로를 구하기 위해 prev 배열을 선언하여 최단경로가 업데이트될 때마다 방문한 노드를 배열에 저장하면 된다.
• 싸이클이 존재하더라도 1에서 n까지 가는 경로에 싸이클이 없으면 가능한 경로가 된다. 이를 구하기 위해 최단 경로를 구하기 전 bfs를 통해 n과 연결된 길의 방문 노드를 체크한다.