PS/C++

[λ°±μ€€/C++] 2098번 μ™ΈνŒμ› 순회

yulee_to 2022. 7. 16. 15:50
728x90

λ°±μ€€
λ°±μ€€
2098번 μ™ΈνŒμ› 순회
2098번 μ™ΈνŒμ› 순회


πŸ€”λ¬Έμ œ 이해

λͺ¨λ“  λ„μ‹œλ₯Ό 거치고 λ‹€μ‹œ 처음 λ„μ‹œλ‘œ λŒμ•„μ˜€λŠ” λͺ¨λ“  경둜 쀑 λΉ„μš©μ΄ κ°€μž₯ 적게 λ“œλŠ” 경둜의 λΉ„μš©μ„ κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€.


πŸ’‘μ²«λ²ˆμ§Έ 아이디어

 

κ·Έλƒ₯ μˆœμ—΄μ„ κ΅¬ν•΄μ„œ ν’€λ©΄ μ΅œλŒ€ 16! =20,922,789,888,000으둜 1초 μ•ˆμ— μ ˆλŒ€ ν’€ 수 μ—†λ‹€.

이 λ¬Έμ œλŠ” 1μ£Όμ°¨ μŠ€ν„°λ””μ—μ„œ 배운 λΉ„νŠΈλ§ˆμŠ€ν‚Ήμ— λŒ€ν•œ λ¬Έμ œμ˜€κ³ , 문제 풀이 방식을 거의 λ‹€ λ°°μ› μ–΄μ„œ DP와 λΉ„νŠΈλ§ˆμŠ€ν‚ΉμœΌλ‘œ λ°”λ‘œ ν’€ 수 μžˆμ—ˆλ‹€.

λ¬Όλ‘  DP λ™μž‘ 방식을 μ΄ν•΄ν•˜κΈ° μœ„ν•΄ μ‹œκ°„μ΄ 쑰금 걸리긴 ν–ˆλ‹€.

 

 

πŸ”₯풀이πŸ”₯

dp[i][j]λŠ” ν˜„μž¬ μœ„μΉ˜ i와 ν˜„μž¬κΉŒμ§€ λ°©λ¬Έν–ˆλ˜ μ •μ λ“€μ˜ 정보λ₯Ό 담은 j 값일 λ•Œ, μ•žμœΌλ‘œ ν•„μš”ν•œ 순회 λΉ„μš©μ˜ μ΅œμ†Ÿκ°’μ„ μ˜λ―Έν•œλ‹€.

jκ°€ (1 << μ •μ μ˜ 개수) -1κ³Ό κ°™μœΌλ©΄ ν˜„μž¬ λͺ¨λ“  정점을 λ°©λ¬Έν–ˆλ‹€λŠ” 것을 μ˜λ―Έν•œλ‹€.

각 정점에 λŒ€ν•΄ μ „λΆ€ λ°©λ¬Έν–ˆμ„ λ•Œμ˜ μ΅œμ†Ÿκ°’μ„ 찾으면 λ˜λ―€λ‘œ 정닡은 dp[처음 정점][1]이닀.

 


μ•„λž˜λŠ” μ œμΆœν•œ μ½”λ“œμ΄λ‹€.

#include <iostream>
#include <cmath>

using namespace std;
#define MAX 1000000000;

int dp[17][65537];
int w[17][17];
int n;

int solve(int cur, int visit) {
    if (visit == (1 << n) - 1 && w[cur][0])
        return w[cur][0];

    if (dp[cur][visit]) return dp[cur][visit];
    dp[cur][visit] = MAX;

    for (int i = 1; i < n; i++) {
        if (visit & (1 << i)) continue;
        if (!w[cur][i]) continue;
        dp[cur][visit] = min(dp[cur][visit], solve(i, visit | (1 << i)) + w[cur][i]);
    }
    return dp[cur][visit];
}


int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> w[i][j];
        }
    }
    cout << solve(0, 1);
}

 

 

728x90