1948번 - 임계경로
주석에 이쁘게 어떻게 코딩했는지 썼으나,
짧게 코멘트를 더해보자면, :)
위상정렬로 풀었습니다.
처음에 인접리스트로 그래프를 받고나서 (v라는 변수에 받아요)
start부터 dfs돌면서 다시 g라는 변수에 그래프를 그려줍니다. 이때 해당 정점의 in-degree를 셌어요.
그 다음 위상정렬 방식처럼 인디그리가 0이되면 큐에 넣고.. 뭐 이런방식을 계속 씁니다.
(싸이클이 없고 일방통행이니까 그래프는 DAG라는 것이고,
그래프에서 start를 거치지 않고 end로 향하는 길이 있을 수 있기 때문에
초기에 dfs를 돌려서 그래프를 다시 생성했거든요.)
ㅠㅠ 고통받는 저를 구원해주세요 ㅠㅠ
어쩜 하나도 그냥 풀리는 게 없을까요 ㅠ?
네.. doju님 덕에 또 해결 ㅋㅋ
1->2->3->5
2->4->5
이런식으로 모든 가중치가 1일때
도로의 개수가 5가 나와야 하는데 6이나오게 짰더라구요.
그래서 맥스구할때 parent저장하고
그 parent따라서 dfs돌리면서 도로 개수 세줬습니다.
도주님 감사. :D
댓글을 작성하려면 로그인해야 합니다.
plzrun 7년 전
주석에 이쁘게 어떻게 코딩했는지 썼으나,
짧게 코멘트를 더해보자면, :)
위상정렬로 풀었습니다.
처음에 인접리스트로 그래프를 받고나서 (v라는 변수에 받아요)
start부터 dfs돌면서 다시 g라는 변수에 그래프를 그려줍니다. 이때 해당 정점의 in-degree를 셌어요.
그 다음 위상정렬 방식처럼 인디그리가 0이되면 큐에 넣고.. 뭐 이런방식을 계속 씁니다.
(싸이클이 없고 일방통행이니까 그래프는 DAG라는 것이고,
그래프에서 start를 거치지 않고 end로 향하는 길이 있을 수 있기 때문에
초기에 dfs를 돌려서 그래프를 다시 생성했거든요.)
ㅠㅠ 고통받는 저를 구원해주세요 ㅠㅠ
어쩜 하나도 그냥 풀리는 게 없을까요 ㅠ?