TSP2 [백준 Gold 1] 2098 외판원 순회 - Java 문제링크 : https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 접근 과정 : 백준 10971 외판원순회2 문제의 코드를 리팩토링 시키는 방향으로 시도해보았다. 완전탐색으로 모든 경우를 탐색하면 시간초과!! 즉, 메모리제이션을 통해 이전에 체크한 부분을 재활용해야 한다. DP[][]을 만들어서 이를 관리 i 도시에 있고 j 비트에 포함된 도시를 탐색한 상황에서, 남은 도시를 모두 방문하는 최소비용 또한, 결국 .. 2021. 12. 22. [백준 Silver 2] 10971 외판원 순회2 - Java 문제링크 : https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 접근 과정 : 한 도시에서 출발하여 모든 도시를 방문한 뒤, 출발 도시로 돌아왔을 때의 비용이 가장 적은 것을 출력하는 문제. 방문체크를 하면서 완전탐색을 하는 방법을 생각 도시의 수가 최대 10개이기에, 비용을 저장한 배열을 그냥 탐색하면서 다음 경로를 추적. 방문체크는 비트를 이용하여 판단 비용을 누적해가면서 경로를 추적하다가, 만약 이.. 2021. 12. 22. 이전 1 다음
