백준 31871번 영일랜드 Java
https://www.acmicpc.net/problem/31871
문제
생각하기
-
외판원 순환문제이다.
-
백트래킹, 조합 문제이다.
동작
DFS와 BFS를 함께 사용하는 문제인가?🧐
처음에 DFS로 조합을 방문 순서 조합을 만들고, BFS로 탐색하려고 했는데, 이미 DFS를 통해 방문 순서를 만들었기 때문에 계산만 하면 되므로 추가적인 탐색은 필요하지 않다.
오일러 회로 문제인가?
문제를 보고 처음에 오일러 회로 문제라고 생각했는데, 오일러 회로 문제도 아니었다.
오일러 회로는 모든 간선을 딱 한 번씩만 지나서 출발점으로 돌아오는 경로이다. 나는 출발점인 정문에 꽂혀서 돌아온다는 부분만 집중했다.
반면, 외판원 순회는 모든 정점을 딱 한 번씩만 지나서 출발점으로 돌아오는 경로이다.
따라서, 놀이기구를 모두 한 번씩 탑승한다는 조건에서 외판원 순회의 정의와 일치한다.
BFS의 방식으로 풀 수 있긴 하다. 그러나 아주 비효율적이고 결국에는 완전 탐색
private static int BFS() {
PriorityQueue<State> que = new PriorityQueue<>();
que.offer(new State(0, new HashSet<>(), 0));
int ans = -1;
while (!que.isEmpty()) {
State cur = que.poll();
if (cur.visited.size() == N + 1 && cur.num == 0) {
ans = Math.max(ans, cur.totalDist);
continue;
}
for (Edge next : adjList.get(cur.num)) {
if (!cur.visited.contains(next.num) || cur.visited.size() == N + 1 && next.num == 0) {
que.offer(new State(next.num, cur.visited, cur.totalDist + next.dist));
}
}
}
return ans;
} // End of BFS()
이런식으로 상태별로 set이 필요하다.
결과
코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N, M, ans;
private static int[][] arr;
private static int[] comb;
private static boolean[] isVisited;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
bw.write(solve());
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
DFS(1, 1);
sb.append(ans);
return sb.toString();
} // End of solve()
private static void DFS(int idx, int depth) {
if (depth == N + 1) {
int sum = 0;
for (int i = 0; i < N + 1; i++) {
if (arr[comb[i]][comb[i + 1]] != -1) {
sum += arr[comb[i]][comb[i + 1]];
} else {
return;
}
}
ans = Math.max(ans, sum);
return;
}
for (int i = idx; i <= N; i++) {
if (isVisited[i]) continue;
isVisited[i] = true;
comb[depth] = i;
DFS(idx, depth + 1);
isVisited[i] = false;
}
} // End of DFS()
private static void input() throws IOException {
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
ans = -1;
comb = new int[N + 2];
isVisited = new boolean[N + 2];
arr = new int[N + 1][N + 1];
for (int i = 0; i <= N; i++) {
Arrays.fill(arr[i], -1);
}
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
arr[a][b] = Math.max(arr[a][b], c);
}
} // End of input()
} // End of Main class
(비효율) 우선순위 큐 사용
import java.io.*;
import java.util.*;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N, M;
private static List<List<Edge>> adjList;
private static Map<Integer, Map<Integer, Integer>> edgeMap;
private static class Edge {
int num;
int dist;
private Edge(int num, int dist) {
this.num = num;
this.dist = dist;
}
} // End of Edge class
private static class State implements Comparable<State> {
int num;
Set<Integer> visited;
int totalDist;
private State(int num, Set<Integer> visited, int totalDist) {
this.num = num;
this.visited = new HashSet<>(visited);
this.visited.add(num);
this.totalDist = totalDist;
}
@Override
public int compareTo(State o) {
if (visited.size() == o.visited.size()) {
return o.totalDist - totalDist;
}
return o.visited.size() - visited.size();
}
} // End of State class
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
bw.write(solve());
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
sb.append(BFS());
return sb.toString();
} // End of solve()
private static int BFS() {
PriorityQueue<State> que = new PriorityQueue<>();
que.offer(new State(0, new HashSet<>(), 0));
int ans = -1;
while (!que.isEmpty()) {
State cur = que.poll();
if (cur.visited.size() == N + 1 && cur.num == 0) {
ans = Math.max(ans, cur.totalDist);
continue;
}
for (Edge next : adjList.get(cur.num)) {
if (!cur.visited.contains(next.num) || cur.visited.size() == N + 1 && next.num == 0) {
que.offer(new State(next.num, cur.visited, cur.totalDist + next.dist));
}
}
}
return ans;
} // End of BFS()
private static void input() throws IOException {
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
adjList = new ArrayList<>();
edgeMap = new HashMap<>();
for (int i = 0; i <= N + 1; i++) {
adjList.add(new ArrayList<>());
edgeMap.put(i, new HashMap<>());
}
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
if (u == v) continue; // 자신한테로 오는 간선은 제거
Map<Integer, Integer> curMap = edgeMap.get(u);
if (curMap.containsKey(v)) {
curMap.put(v, Math.max(curMap.get(v), d));
} else {
curMap.put(v, d);
}
}
for (int i = 0; i <= N; i++) {
Map<Integer, Integer> con = edgeMap.get(i);
for (int key : con.keySet()) {
int d = con.get(key);
adjList.get(i).add(new Edge(key, d));
}
}
} // End of input()
} // End of Main class
