백준 2098번 외판원 순회
< 백준 2098번 외판원 순회 - 마포 코딩박 >
사용한 알고리즘: 비트 마스킹, DP
외판원 순회문제는 매우 유명한 비트마스킹 문제입니다. 한 도시에서 출발하여 모든 도시를 들러서 다시 처음 도시로 올 것이므로 어떤 도시에서 출발하든 순회 비용이 같습니다.
문제풀이는 다음과 같습니다.
(1) (코드 7~8)
'dp[k][visited] : k: 현재 도시, visited: 방문했던 도시들 상태에서 순회를 마치는데 드는 최소비용' 이라고 설정하였습니다.
방문도시(visited)는 2진법 형태로 저장합니다.
예를 들어 1번도시, 3번도시, 16번도시를 방문한 상태는 1000000000000101 로 저장되어 있습니다.
(2) (코드 10~30)
dp값을 계산해 줍니다. 어떤 도시에서 출발하든 순회비용은 변함없으므로 1번도시(index=0) 에서 출발했습니다.
현재 도시와 연결된 방문하지 않은 모든 도시를 재귀적으로 방문합니다.
모든 도시를 방문하고 다시 출발도시 (1번도시) 로 돌아오는 경우를 기저값입니다.
i도시 방문 여부는 저장해놓은 visited | (1<<i) 로 or 연산으로 합니다.
모든 도시 방문여부는 visited == (1<<N)-1 로 합니다. 참고로 (1<<N)-1 = 111...1 (1이 N개) 입니다.
사용한 알고리즘: 비트 마스킹, DP
외판원 순회문제는 매우 유명한 비트마스킹 문제입니다. 한 도시에서 출발하여 모든 도시를 들러서 다시 처음 도시로 올 것이므로 어떤 도시에서 출발하든 순회 비용이 같습니다.
문제풀이는 다음과 같습니다.
(1) (코드 7~8)
'dp[k][visited] : k: 현재 도시, visited: 방문했던 도시들 상태에서 순회를 마치는데 드는 최소비용' 이라고 설정하였습니다.
방문도시(visited)는 2진법 형태로 저장합니다.
예를 들어 1번도시, 3번도시, 16번도시를 방문한 상태는 1000000000000101 로 저장되어 있습니다.
(2) (코드 10~30)
dp값을 계산해 줍니다. 어떤 도시에서 출발하든 순회비용은 변함없으므로 1번도시(index=0) 에서 출발했습니다.
현재 도시와 연결된 방문하지 않은 모든 도시를 재귀적으로 방문합니다.
모든 도시를 방문하고 다시 출발도시 (1번도시) 로 돌아오는 경우를 기저값입니다.
i도시 방문 여부는 저장해놓은 visited | (1<<i) 로 or 연산으로 합니다.
모든 도시 방문여부는 visited == (1<<N)-1 로 합니다. 참고로 (1<<N)-1 = 111...1 (1이 N개) 입니다.
코드 10번째 줄에
답글삭제int &ret = dp[current][visited]; 여기서 ret앞에 &가 있어야 하는 이유가 뭔지 알 수 있을까요?
우선 ret이란걸 쓰는 이유는 dp[current][visited]가 너무길어서 쓰기 힘들어서입니다.
삭제&ret = dp[current][visited] 라고 받을 경우, ret과 dp[current][visited]는 한몸이 된다고 생각하시면 편할 것 같습니다.
즉, ret +=1 을 해주면 dp[current][visited]+1 이 됩니다.
&없이 ret = dp[current][visited] 라고 받을 경우, ret 은 '값'만 새로 받기 때문에
ret을 변화시켜도 dp값이 변화되지 않습니다.
https://modoocode.com/23
위 링크를 보시면 보다 확실한 설명이 되어 있어요!
(블로그 첫 댓글인데 답글이 늦어서 죄송해요...)
덕분에 잘 이해하고 갑니다.
답글삭제좋은 글 감사드립니다!