https://www.acmicpc.net/problem/1238
1238번: 파티
문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때
www.acmicpc.net
문제는 백준 알고리즘 사이트에서 확인하세요~
문제 분석
N개의 마을중에 X번째 마을에서 파티를 열면 모든 마을에 사람들이 X번째 마을로 왔다가 다시 가는 거리의 최대값을 구하는 문제입니다.
얼핏 보면 최장거리 문제 같지만 자세히 읽어보면 각각의 n (Such that a element in N)에 대해 n에서 출발해서 x로 갔다가 다시 n으로 돌아오는 거리중 가장 긴 값을 찾는 문제에요.
그럼 이 문제를 해결하기 위해 해야할 일은 n에서 x까지 갔다가 x에서 n으로 오는 최단경로를 찾는 것입니다!
어떻게 구할 수 있을까요?
저는 다익스트라를 사용했습니다.
다익스트라는 단일 발신지 최단경로 알고리즘인데요.
x를 단일 발신지로 삼으면 그래프에 있는 모든 정점으로 가는 최단 경로를 구할 수 있어요~
문제의 예제를 그림으로 표현하면 아래와 같습니다
정점 2를 발신지로 잡고 dijkstra를 위한 touch 공간과 length 공간을 생성합니다.
| 1 | 2 | 3 | 4 | |
| length | 1 | - | 5 | - |
| touch | 2 | - | 2 | 0 |
1번 정점이 최단거리군요. 1번 정점을 다음 방문지로 삼습니다~
Dijkstra 는 Single Source Shortest Path 알고리즘이라 항상 단일 발신지에서 출발한다는 점 알아두어야 합니다~
| 1 | 2 | 3 | 4 | |
| length | 1 | -1 | 3 | 8 |
| touch | 2 | - | 1 | 1 |
한번 지나간 곳은 다시 되돌아가지 않으므로 2번 정점에 대한 length space를 -1로 바꾸어줍니다.
다음 정점 방문을 위해 최소값을 조사합니다. 3번 정점이 가진 length가 가장 작군요!
| 1 | 2 | 3 | 4 | |
| length | -1 | -1 | 3 | 7 |
| touch | 2 | - | 1 | 3 |
이로서 x마을에서 파티를 하고 각자의 집으로 돌아가는 최단거리 경로를 모두 찾았습니다
4에서 갈 수 있는 정점은 없습니다
각자의 집에서 x마을로 가는 최단거리 경로는 어떻게 구할 수 있을까요?
힌트를 적자면..! 유향그래프의 간선방향을 반대로 변형하고 dijkstra를 수행하면 답을 구할 수 있습니다.
'Algorithms > Baekjoon Algorithms' 카테고리의 다른 글
| 백준 알고리즘 2302번 문제 : 극장 좌석 (0) | 2019.07.10 |
|---|---|
| 백준 알고리즘 2580번 문제 : 스도쿠 (0) | 2019.07.08 |
| 백준 알고리즘 9869 - Milk Scheduling (0) | 2019.07.01 |
| 백준 알고리즘 2573 - 빙산 (0) | 2019.06.28 |
| 알고리즘 설계 - 동적계획법 (Dynamic Programming) (0) | 2019.06.26 |
