쵼쥬
2022. 5. 6. 22:27
현재 방 == TRAP 이고 이동할 방 == TRAP 인 경우
현재 방 == TRAP 이고 이동할 방 != TRAP 인 경우
현재 방 != TRAP 이고 이동할 방 == TRAP 인 경우
현재 방 != TRAP 이고 이동할 방 != TRAP 인 경우
크게 네가지로 나눠서 생각했다.
그 다음 각 경우 내부에서 현재 방, 이동할 방 중 TRAP이 2개 또는 0개 인 경우와 1개인 경우 이 두가지로 나눠서 풀이 했다.
package com.company;
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
Solution s = new Solution();
System.out.println(s.solution(5, 1, 5, new int[][]{{1, 2, 1}, {2, 3, 1}, {3, 2, 1}, {3, 5, 1}, {1, 5, 10}}, new int[]{3}));
}
static class Solution {
public int solution(int n, int start, int end, int[][] roads, int[] traps) {
int answer = 0;
int[][] arr = new int[n + 1][n + 1];
int[][] check = new int[n + 1][3];
for (int[] i : roads) {
arr[i[0]][i[1]] = arr[i[0]][i[1]] == 0 ? i[2] : Math.min(arr[i[0]][i[1]], i[2]);
}
int[][] t = new int[traps.length + 1][2];
t[0][0] = start;
for (int i = 1; i < t.length; i++) {
t[i][0] = traps[i - 1];
t[i][1] = 1;
}
PriorityQueue<int[][]> pq = new PriorityQueue<>((o1, o2) -> o1[0][1] - o2[0][1]);
pq.add(t);
while (!pq.isEmpty()) {
int[][] node = pq.poll();
System.out.println(node[0][0]);
int indexA = findIndex(node, node[0][0]);
if (indexA == -2 && check[node[0][0]][0] == 4 || indexA != -2 && check[node[0][0]][node[indexA][1] + 1] == 4) {
continue;
}
if (indexA == -2) {
check[node[0][0]][0]++;
} else {
check[node[0][0]][node[indexA][1] + 1]++;
}
if (node[0][0] == end) {
answer = node[0][1];
break;
}
for (int i = 1; i <= n; i++) {
if (i == node[0][0]) {
continue;
}
int indexB = findIndex(node, i);
int[][] temp = new int[node.length][2];
for (int j = 0; j < temp.length; j++) {
temp[j] = node[j].clone();
}
temp[0][0] = i;
if (indexA != -2 && indexB != -2) {
if ((node[indexA][1] == -1 && node[indexB][1] == -1 || node[indexA][1] == 1 && node[indexB][1] == 1) && arr[node[0][0]][i] > 0) {
temp[0][1] = node[0][1] + arr[node[0][0]][i];
temp[indexB][1] = -temp[indexB][1];
pq.add(temp);
} else if (node[indexA][1] == 1 || node[indexB][1] == 1) {
int x = arr[node[0][0]][i];
arr[node[0][0]][i] = arr[i][node[0][0]];
arr[i][node[0][0]] = x;
if (arr[node[0][0]][i] > 0) {
temp[0][1] = node[0][1] + arr[node[0][0]][i];
temp[indexB][1] = -temp[indexB][1];
pq.add(temp);
}
arr[i][node[0][0]] = arr[node[0][0]][i];
arr[node[0][0]][i] = x;
}
} else if (indexA != -2) {
if (node[indexA][1] == -1) {
int x = arr[node[0][0]][i];
arr[node[0][0]][i] = arr[i][node[0][0]];
arr[i][node[0][0]] = x;
if (arr[node[0][0]][i] > 0) {
temp[0][1] = node[0][1] + arr[node[0][0]][i];
pq.add(temp);
}
arr[i][node[0][0]] = arr[node[0][0]][i];
arr[node[0][0]][i] = x;
} else if (node[indexA][1] == 1 && arr[node[0][0]][i] > 0) {
temp[0][1] = node[0][1] + arr[node[0][0]][i];
pq.add(temp);
}
} else if (indexB != -2) {
if (node[indexB][1] == -1) {
int x = arr[node[0][0]][i];
arr[node[0][0]][i] = arr[i][node[0][0]];
arr[i][node[0][0]] = x;
if (arr[node[0][0]][i] > 0) {
temp[0][1] = node[0][1] + arr[node[0][0]][i];
temp[indexB][1] = -temp[indexB][1];
pq.add(temp);
}
arr[i][node[0][0]] = arr[node[0][0]][i];
arr[node[0][0]][i] = x;
} else if (node[indexB][1] == 1 && arr[node[0][0]][i] > 0) {
temp[0][1] = node[0][1] + arr[node[0][0]][i];
temp[indexB][1] = -temp[indexB][1];
pq.add(temp);
}
} else if (arr[node[0][0]][i] > 0) {
temp[0][1] = node[0][1] + arr[node[0][0]][i];
pq.add(temp);
}
}
}
return answer;
}
}
static int findIndex(int[][] node, int num) {
for (int i = 1; i < node.length; i++) {
if (node[i][0] == num) {
return i;
}
}
return -2;
}
}