[BOJ 24519] 백준 24519번 - Bottleneck Travelling Salesman Problem (Large)

		2022 ICPC Sinchon Winter Algorithm Camp Contest 풀이
A		[BOJ 24510] 시간복잡도를 배운 도도
B		[BOJ 24509] 상품의 주인은?
C		[BOJ 24511] queuestack
D		[BOJ 24512] Bottleneck Travelling Salesman Problem (Small)
E		[BOJ 24513] 좀비 바이러스
F		[BOJ 24514] n번째 숫자 찾기
G		[BOJ 24515] 히히 못가
H		[BOJ 24516] 잘 알려진 수열 구하기
J		[BOJ 24517] 카드 게임과 쿼리
K		[BOJ 24519] Bottleneck Travelling Salesman Problem (Large)

1. 문제

$24519$. Bottleneck Travelling Salesman Problem (Large) (2022 ICPC Sinchon Winter Algorithm Camp Contest K번)

백준 24519번 - Bottleneck Travelling Salesman Problem (Large) (https://www.acmicpc.net/problem/24519)

2. 풀이

외판원 순회 문제와 매우 유사하다.

백준 2098번 - 외판원 순회 (https://www.acmicpc.net/problem/2098)

외판원 순회는 이동 경로의 최솟값을 찾는 문제이고, 이 문제는 정점 간 이동 비용의 최댓값의 최솟값을 찾는 문제이다.

따라서, 외판원 순회 코드에서 bitmasking dp 방식의 틀은 유지하되, 이전 dp 값을 받아서 다음 dp 값을 갱신하는 부분의 코드를 바꿔주면 된다. 이전 dp값과 다음 노드로 이동하는데 드는 비용의 최댓값이 최소가 되는 곳을 찾도록 만들어 준다.

값 뿐만 아니라 경로도 출력해야 한다. 따라서 backtracking(역추적)을 수행한다. 역추적 함수 또한 dp를 수행하는 함수와 동일한 맥락이다.

현재 dp값, 나중 dp값, 현재 비용을 토대로 문제의 조건에 만족하는지 확인하고, 만족하면 그 경로로 간 것이므로 해당 경로를 저장하면 된다.

3. 채점 결과

4. 회고

처음엔 backtracking을 각각의 dp에 이동 경로를 일일이 저장하는 방식으로 아예 잘못 접근해서 TLE를 받았다.

이후에는 경로를 저장하는 방법이 틀려서 WA를 받았고, 정답 경로를 찾아도 코드를 계속 돌려버려서 TLE를 받았다.

정답을 찾자마자 출력하는 방식으로 바꾸어서 WA와 TLE를 동시에 해결하였다.

5. 코드