๋ฌธ์
https://www.acmicpc.net/problem/17182
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x1C๊ฐ - ํ๋ก์ด๋ ์๊ณ ๋ฆฌ์ฆ
์๊ณ ๋ฆฌ์ฆ: ๋ธ๋ฃจํธํฌ์ค ์๊ณ ๋ฆฌ์ฆ, ์ต๋จ ๊ฒฝ๋ก, ๋นํธ๋ง์คํน, ๋ฐฑํธ๋ํน, ํ๋ก์ด๋-์์
ํ์ด

"๋ชจ๋ ํ์ฑ์ ํ์ฌํ๋๋ฐ" ๊ฑธ๋ฆฌ๋ ์ต์ ์๊ฐ์ ๊ตฌํด์ผํ๋ค.
๋จ, ์ถ๋ฐ์ง๋ก ๋์์ฌ ํ์๋ ์์ผ๋ฉฐ ์ด๋ฏธ ๋ฐฉ๋ฌธํ ํ์ฑ๋ "์ค๋ณตํด์" ๊ฐ ์ ์๋ค.
๐ ์ ์กฐ๊ฑด๋๋ฌธ์ "์ต์ ์ ์ฅ ํธ๋ฆฌ" ๋ฌธ์ ์ธ ์ค ์์์ผ๋ ๊ฒฐ์ ์ ์ธ ์ฐจ์ด๊ฐ ์๋ค!
ํ ๋ฒ ๋ฐฉ๋ฌธํ ๊ณณ์ ๋ฐ๋ก ๋น์ฉ์ด ๋ฐ์ํ์ง ์๋ ์ต์ ์ ์ฅ ํธ๋ฆฌ์ ๋ฌ๋ฆฌ, ์ฌ๋ฐฉ๋ฌธ์ด ๊ฐ๋ฅํ๊ธด ํ์ง๋ง ๋น์ฉ์ด ๋ฐ์ํ๋ ๊ตฌ์กฐ๋ค.
๋ฐ๋ผ์ 1) ํ๋ก์ด๋ ์์
๋ก ๊ฐ ํ์ฑ๊ฐ์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๊ณ , 2) ๋ฐฉ๋ฌธํ์ง ์์ ํ์ฑ๋ค ์ค ํ์ฌ ํ์ฑ์ผ๋ก๋ถํฐ ์์ ์๊ฐ์ด ๊ฐ์ฅ ์งง์ ํ์ฑ์ ์ ํํ๋ค.
์ฐธ๊ณ ๋ก DP(๋ฉ๋ชจ์ด์ ์ด์
) + ๋นํธ๋ง์คํน์ ์ ์ฉํ๋ฉด ํจ์ฌ ๋นจ๋ผ์ง๋ค.dp[curr][visited]: ํ์ฌ ํ์ฑ curr์์ ์์ํด์, ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ๋ชจ๋ ํ์ฑ์ ํ์ฌํ๋๋ฐ ํ์ํ ์ต์ ์๊ฐ
curr(ํ์ฌ ํ์ฑ): ํ์ฌ ํ์ฌ์ ์ด ์์นํ ํ์ฑ ๋ฒํธvisited(๋ฐฉ๋ฌธ ์ํ): ์ง๊ธ๊น์ง ๋ฐฉ๋ฌธํ ํ์ฑ๋ค์ ๋ํ๋ด๋ ๋นํธ๋ง์คํฌ
์คํ ๊ณผ์ ์ ์๋์ ๊ฐ๋ค.
- ๋ชจ๋ ๊ฐ์ a-b๋ฅผ ๋์์ผ๋ก ํ๋ก์ด๋ ์์ ์ํ
- ์ถ๋ฐ ํ์ฑ ๋ฐฉ๋ฌธ์ฒดํฌ ํ, ๊ธฐ์ ์ผ๋ก DFS ์คํ
- ๋ชจ๋ ํ์ฑ์ ๋ฐฉ๋ฌธํ๋ค๋ฉด 0 ๋ฐํ
- DP์
[curr][visited]๊ฐ์ด ์๋ค๋ฉด ํด๋น ๊ฐ ๋ฐํ - ์ ๊ฒฝ์ฐ์ ํด๋น๋์ง ์์ ๊ฒฝ์ฐ, ์ฌ๊ท์ ์ผ๋ก DFS ์คํ
- ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ํ์ฑ๋ค์ ํ๋์ฉ ์ ํ
- ํ์ฌ ํ์ฑ-์ ํํ ํ์ฑ๊ฐ์ ๊ฑฐ๋ฆฌ๊ฐ + dfs(์ ํํ ํ์ฑ, ํด๋น ํ์ฑ์ ๋ฐฉ๋ฌธ์ฒ๋ฆฌํ visited)๊ฐ ๋น๊ต
- ๊ฐ์ฅ ์ต์ ์ ๊ฐ์
dp[curr][visited]๊ฐ์ผ๋ก ์ ์ฅ dp[curr][visited]๋ฐํ
์ ์ฒด ์ฝ๋
# ๋ฉ๋ชจ๋ฆฌ: 32412KB / ์๊ฐ: 44ms
from sys import stdin
input = stdin.readline
INF = int(1e9)
N, K = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
# 1. ํ๋ก์ด๋-์์
๋ก ๋ ํ์ฑ๊ฐ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํด์ค.
for k in range(N):
for i in range(N):
for j in range(N):
graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])
# 2. DP๋ก ์ต์ ์ ๊ฒฝ๋ก๋ฅผ ๊ตฌํจ
# dp[curr][visited] = ํ์ฌ ํ์ฑ curr์์ ์์ํด์, ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ๋ชจ๋ ํ์ฑ์ ํ์ฌํ๋๋ฐ ํ์ํ ์ต์ ์๊ฐ
dp = [[-1] * (1 << N) for _ in range(N)]
def find(curr, visited):
if visited == (1 << N) - 1:
return 0
if dp[curr][visited] != -1:
return dp[curr][visited]
dp[curr][visited] = INF
for nxt in range(N):
# ๋ฐฉ๋ฌธํ์ง ์์ ํ์ฑ์ผ๊ฒฝ์ฐ
if not (visited & (1 << nxt)):
cost = graph[curr][nxt] + find(nxt, visited | (1 << nxt))
dp[curr][visited] = min(dp[curr][visited], cost)
return dp[curr][visited]
print(find(K, 1 << K))
๊ทธ๋ฆฌ๊ณ ์ง๋ฌธ ๊ฒ์ํ์ ์ดํด๋ณด๋ค๊ฐ ๋ฐ๊ฒฌํ ๊ธ์ธ๋ฐ, DP ์ดํด์ ๋์์ด ๋ ๊ฒ ๊ฐ๋ค.
(์ถ์ฒ:https://www.acmicpc.net/board/view/156743)
Q. "ํ๋ก์ด๋-์์ ๋ก A → C๊ฐ A → B → C๋ก ๊ฐฑ์ ๋์๋๋ฐ, A์์ ์์ํด์ C๋ฅผ ๋ฐฉ๋ฌธํ๋ค๋ฉด A -> B -> C๋ฅผ ๋ฐฉ๋ฌธํ ๊ฒ์ด ๋๋๋ฐ... ์ B๋ฅผ ๋ฐ๋ก ๋ฐฉ๋ฌธ์ฒ๋ฆฌ ํด์ค์ผ ํ๋์?"
A. ๊ตฌํ ๋ฐฉ์์ ๋ฐ๋ผ ์ฐจ์ด๊ฐ ์์๊ฒ ๊ฐ์ง๋ง
dp[ํ์ฌํ์ฑ][๋ฐฉ๋ฌธํ ํ์ฑ๋ค] ๊ณผ ๊ฐ์ด ์ ์ธํ๊ณ , ํ์ฌ ํ์ฑ์์ ์ด๋ํ ์ ์๋ ๋ค์ํ์ฑ๋ค์ ๋ชจ๋ ๋ฐ๋ผ๋ณด๋๋ก ํ๋ค๋ฉด
A → B → C๋ก ์ค์ ๋ก ์ด๋ํ๋ค๊ณ ํด์ B๋ฅผ ๊ณ ๋ คํ๋ ๊ฒ์ ๋ถํ์ํ ํ๋์ด๋ผ๊ณ ์๊ฐ๋ฉ๋๋ค.
๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๋ฐ๋ผ๋ณด๊ฒ ๋๋ฉด A → B ์ด๋ B → C ์ด๋ํ๋ ๊ฒฝ์ฐ๊ฐ ์์ํ
๋๊น์
์ง๋ฌธ๊ธ ๋(?)์ ๋๋ ํท๊ฐ๋ฆฌ๋๋ฐ... ๊ฒฐ๋ก ์ ํ๋ก์ด๋ ์์ ์์์ A → C ๊ฐฑ์ (A→B→C)๊ณผ DP์์์ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ ๋ณ๊ฐ์ธ ๊ฒ.
๊ทธ๋ฆฌ๊ณ ์ด์ฐจํผ DP๊ฐ ์์์ ์ ์ฒด์ ์ผ๋ก ๋ ํจ์จ์ ์ธ ์ต์ ์ ๊ฐ์ ์ ํํ๋ค.