[BOJ 24512] 백준 24512번 - Bottleneck Travelling Salesman Problem (Small)

		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. 문제

$24512$. Bottleneck Travelling Salesman Problem (Small) (2022 ICPC Sinchon Winter Algorithm Camp Contest D번)

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

2. 풀이

백준 2098번 외판원 순회 문제가 살짝 변형된 문제이다.

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

기존의 문제는 가장 적은 비용을 들이는 순회 경로의 비용을 구하는 문제인데, 이는 정점 간 이동 비용의 최댓값의 최솟값을 찾아야 하고 거기에 경로까지 출력해야 한다.

따라서 bitmask dp 방법을 그대로 채용하고 재귀를 나올 때 값 갱신하는 코드만 수정해주면 답을 구할 수 있다. 백트래킹 작업 또한 dp 탐색할 때와 동일하게 진행하면서 경로를 찾아가면 된다.

다만, 해당 문제는 (Small) 문제로 $N\leq 9$여서, 브루트포스 방식으로 구현해도 충분하다고 한다. 이 문제는 백준 24519번 (Large) 문제를 풀기 위한 예비 작업일 뿐이다. 나는 브루트포스 방식으로 구현하지 않고 한번에 bitmask dp로 풀었기 때문에 24519번과 묶어서 한번에 살펴보고자 한다. 때문에 따로 이 문제에 대한 코드는 없다.

백준 24519번 - Bottleneck Travelling Salesman Problem (Large) 풀이 (https://burningfalls.github.io/algorithm/boj-24519/)

3. 채점 결과

4. 회고

.

5. 코드

.