[백준 1238 C++] 파티

오늘은 백준(BOJ) 1238번 파티 문제에 대해 다뤄볼 예정이다.

파티 문제 링크 (백준(BOJ) 1238번 문제): https://www.acmicpc.net/problem/1238

1238번: 파티

문제 설명 

백준 1238번 파티 문제는 여러 집들 중 특정 X 집에서 파티를 할 경우, 파티를 하는 집에 갔다가 집으로 돌아오는데 가장 오래 걸리는 시간을 구하는 문제이다. 

문제 풀이 

백준 1238번 파티 문제에서 특정 X 집으로 이동할 때와 집으로 돌아갈 때 모두 최단 경로로 이동하므로, 이 문제는 다익스트라 알고리즘(Dijsktra Algorithm)을 사용하여 해결할 수 있다. 

 

쓴이는 아래와 같은 방식으로 문제를 해결하였다.

 

1. 집에서 특정 X 집까지 도달하는데 걸리는 시간 -> 각 집마다 다익스트라 수행 

2. 특정 X에서 집까지 도달하는데 걸리는 시간 -> 특정 X에서 다익스트라 1번 수행 

 

위 과정을 진행한 후, 두 경로를 거칠 때 걸리는 시간을 더하였을 때 나오는 최댓값을 구해주었다. 

이를 코드로 나타내면 아래와 같다.