BOJ 여행 가자2 [BOJ]1976번: 여행 가자 문제: https://www.acmicpc.net/problem/1976 N제한이 작으므로 완전 탐색으로 해결할 수 있습니다. 여행 계획 E-C-B-C-D를 예시로 설명해보면, 여행 계획을 출발지-도착지 관계로 E-C, C-B, B-C, C-D로 나눈 후 각 각을 방문할 수 있는지 DFS로 조사합니다. 시간복잡도는 O(N^2*M)으로 최악의 경우에도 O(40,000,000)이므로 시간 제한에 걸리지 않습니다 :) 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1976.java 2022. 3. 2. [BOJ]1976번: 여행 가자 www.acmicpc.net/problem/1976 여러 가지 방법으로 풀 수가 있겠습니다. 제가 해결한 방법은 Floyd + BFS 입니다. 1. 플로이드를 통해 모든 가능한 정점쌍을 연결해줍니다. 2. 주어진 플로이드를 가지고 N개의 노드에 대해 BFS를 돌아서 컴포넌트를 나눠줍니다. 3. 여행 경로에 속한 노드가 모두 한 컴포넌트에 속해있다면 순서가 어떻든 모두 방문이 가능합니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1976.cc 2020. 10. 6. 이전 1 다음
