출처 https://www.acmicpc.net/problem/24042풀이 전략이 문제의 경우 일반적인 dijkstra 문제와는 살짝 다르다.신호등이 바뀌는 순서를 고려할 뿐더러 만약 경로에 순서가 늦는 신호등이 있는 경우 신호등의 주기만큼 기다려야 한다.따라서 일반적인 Dijkstra 알고리즘의 틀에서 cost를 계산하는 부분을 잘 계산해야한다.풀이왼쪽에 있는 첫 번째 예제의 경우 1-4 로 가는 최단 경로는 1-4 방향 신호등이 4번째에 바뀌기 때문에 정답은 4인 것을 쉽게 알 수 있다.그러나 오른쪽에 있는 두 번째 예제의 경우 1-8로 한번에 가는 경로가 없기 때문에 여러 신호등을 거쳐 가야하므로 고려해야할 부분이 많다.먼저 정답이 되는 경우의 계산 방식을 보면,1-2 횡단보도가 7번째에 바뀌기 ..

출처https://www.acmicpc.net/problem/1504풀이 전략Dijkstra 알고리즘을 이용하여 최단경로를 구할 것이다. 다만, 이 문제의 경우 마지막에 입력 받는 v1과 v2를 무조건적으로 거친 경로 중 최단 경로를 찾는 것이기 때문에 세 가지 경우로 나누어서 구할 것이다.from 1번 (시작 정점) to v1from v1 to v2from v2 to N번 (도착 정점)세 가지의 경우로 나눈 최단 경로를 모두 더해주면 정답이 구해질 것이라고 생각하고 문제를 접근했다풀이문제의 예시를 그림으로 그려보면 위의 그림과 같다. 첫번째 예시를 보면 2-3을 지나는 최단경로를 찾으면 1-2-3-4로 총 합은 7이 된다. 이 경우, 모든 vertex가 연결되어 있기 때문에 인접노드행렬을 그려보면 IN..