미로탈출

---

현재 방 == 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;
    }
}