문제
https://www.acmicpc.net/problem/23817
23817번: 포항항
첫번째 예제의 경우 오른쪽 3칸, 왼쪽 1칸, 아래쪽 3칸, 오른쪽 1칸, 왼쪽 3칸으로 총 11칸 이동하여 5개의 식당을 방문할 수 있다. 두번째 예제의 경우 장애물에 가로막혀 5개의 식당을 방문할 수
www.acmicpc.net
풀이과정
1. bit dp?
식당수가 20개이므로 생각할 수 있다.
식당을 인덱싱해주고 식당을 발견하면 그 인덱스 bit을 on해준다.
각 bit별로 bfs한 정보(거리정보)를 저장한다.
지도가 최대 1000*1000이므로 이 풀이는 불가능하다.
2.other
우린 식당을 방문했는가가 중요하므로 식당사이의 거리가 중요하다. 다른 빈 공간의 거리는 중요하지않다.
따라서 bfs(거리정보)를 시작점과 모든 식당을 기준으로 구해주면 된다.
그렇다면, 식당과 시작점이 정점이고 가중치는 각각의 거리인 그래프를 얻을 수 있다.
정점이 최대 21개가 됐다.! 그리고 그중 하나는 시작점으로 고정돼있다. K를 총 식당의 수라고하자.
문제를 바꿔보자.
"정점이 0번부터 K번까지 있는 그래프가 있다. 입력으로 인접행렬이 주어진다. 값이 -1이면 연결이 안된것이다. 그게 아니라면 가중치이다. 0번에서 무조건 시작해야 할때 0번을 제외한 정점 5개를 방문하는 경로 중 가중치합이 최소일떄를 구하여라"
웰노운 백트래킹 문제가 됐다.
'알고리즘문제풀이' 카테고리의 다른 글
| 백준 30870 사이클 없는 그래프 만들기 (2) | 2023.12.07 |
|---|---|
| solved.ac Grand Arena #3 div2 문제 후기 (0) | 2023.11.28 |
| 백준 13010 h(n) (0) | 2023.11.16 |
| 백준 30510 토마에함수 (0) | 2023.11.12 |
| 백준 7868 해밍 수열 (2) | 2023.11.12 |