목록2024/12/01 (1)

공부 흔적남기기

[JAVA] 백준 특정한 최단 경로 1504

최단 거리 문제이다. 최단 거리 문제는 보통 BFS를 통해서 구할 수 있는데 BFS를 이용하면 DFS보다 그래프의level 단위로 검사하기 때문에 일반적으로 더 빠르고 안정적으로 최단거리를 구할 수 있다. 이떄 가중치가 존재한다면 다익스트라, 벨만포드, 플로이드중 하나를 사용해야하는데 이 문제는 시작점이 3개로 고정이고, 음수 사이클이 존재하지 않기 때문에 다익스트라를 통해서 구현하면 된다. 문제 설명 1에서 N까지 움직이는데 경유점 c1, c2를 반드시 거쳐서 도달해야한다그럼 총 2가지 경우의 수가 나올 것이다 1 -> c1 -> c2 -> N1 -> c2 -> c1 -> N 1에서 시작하는 최단거리 c1에서 시작하는 최단거리 c2 에서 시작하는 최단 거리를 구한후 2가지 경우에 대해 MAX 값을 처리..
코테/백준 2024. 12. 1. 23:50
이전 Prev 1 Next 다음