글 읽기 - DP 완전탐색으로 접근했는데 틀렸습니다.

msg016 2년 전 0

임의의 두 지점 사이의 경로가 1 ~ N - 1개 일 때를 모두 구해 더해주는 방식으로 접근했습니다.

만약 N이 4라면,

우선 DP[1]에 기존에 주어진 값을 모두 입력합니다. 0일 때는 INF(987654321)로 치환하였습니다.

이후 2 ~ N - 1까지 순회하면서, 플로이드-워셜 알고리즘같이 경유지를 잡아가며 최저값을 계산합니다.

출발지 경유지 도착지가 중복되는 경우 계산하지 않으며, 갱신될 경우 방문 지점 비트마스킹도 갱신했습니다.

게시판 반례는 다 정상출력되는데, 6%에서 틀렸습니다.

시간초과 메모리초과도 아니고 틀렸습니다라서 진짜 모르겠네요. 도와주시면 감사드리겠습니다.

const INF = 987654321;

function main() {
    const [n, ...input] = require('fs').readFileSync("input.txt").toString().trim().split("\n");
    const N = Number(n.trim());
    const MAP = input.map((el) => (
        el.trim().split(" ").map(Number)
    ))

    // DP[노드 사이 경로의 수][출발점][도착점][최소 거리, 방문지점(비트마스킹)]
    const DP = Array.from({length : N}, () => (
        Array.from({length: N}, () => (
            Array.from({length: N}, () => (
                [INF, 0]
            ))
        ))
    ))

    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            DP[1][i][j][0] = MAP[i][j] === 0 ? INF : MAP[i][j];
            DP[1][i][j][1] |= (1 << i);
            DP[1][i][j][1] |= (1 << j);
        }
    }
    
    for (let i = 2; i < N; i++) { // 사이 경로의 수. 모든 정점이 이어지는데에는 N - 1개의 경로.
        for (let j = 0; j < N; j++) { // 출발지.
            for (let k = 0; k < N; k++) { // 도착지.
                if (j === k) continue; // 출발지와 도착지가 같으면 탐색하지 않음.
                for (let l = 0; l < N; l++) { // 경유지.
                    if (l === k || l === j) continue; // 경유지가 출발지 또는 도착지와 같다면 탐색하지 않음.
                    for (let m = 1; m < i; m++) {
                        // 두 경로가 경유지 말고 다른 지점을 공유한다면 되돌아가는 것이므로 탐색하지 않음.
                        if ((DP[m][j][l][1] & DP[i - m][l][k][1]) !== (1 << l)) continue; 

                        if (DP[i][j][k][0] >  DP[m][j][l][0] + DP[i - m][l][k][0]) {
                            DP[i][j][k][0] = DP[m][j][l][0] + DP[i - m][l][k][0];
                            DP[i][j][k][1] = DP[m][j][l][1] | DP[i - m][l][k][1];
                        }
                    }
                }
            }
        }
    }

    // 두 지점 사이 경로가 N - 1인 값에 돌아가는 경로(j -> i)까지 더해 가장 최소인 값을 출력.
    let min = INF;
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (i === j || DP[N-1][i][j][1] !== ((1 << N) - 1)) continue;
            min = Math.min(DP[N-1][i][j][0] + DP[1][j][i][0], min);
        }
    }

    console.log(min);
}

main();

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

DP 완전탐색으로 접근했는데 틀렸습니다.

msg016 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말