TSP 썸네일형 리스트형 백준 2098 외판원 순회 백준 문제를 다시 잡아봤다. DP문제에서 진짜 엄청 유명한 문제인 TSP를 풀어보고 싶어서 찾았다. 근데 진짜 TSP 키워드로 구글에서 검색하면 별의 별 곳 응용이 다 나오더라. 가장 많이 보이는게 경로 문제, 최근 드론 배달이 많이 연구 되고 있는데 그쪽 관련된 이미지가 많이 나오는 것 같다. 문제는 심플하다. 유향 가중치 그래프를 인접 행렬로 입력 받아서, 모든 노드를 방문하고 제 자리로 돌아오는 경로를 찾는 것 - 이 문제에서는 비용만 구하면 된다. 처음 접근은 DFS를 사용해서 DP에 저장해가면서 풀어보는 방식이었다. 직전 문제인 도둑질에서도 같은 접근 방법을 사용했었다. 근데 코드 구현 중, 탐색 중간에 되돌아가거나 다음 경로가 없을 때 너무 복잡해져서 엎었다... 그래서 이걸 어떻게 하나..... 더보기 이전 1 다음