2021년 08월 21일 TIL

오늘은 알고리즘 문제를 하루종일 풀었다.

간만에 알고리즘 문제를 푸니 굉장히 재미있었다. 오늘 특히 시간을 많이 소요한 문제는,

카카오 인턴십 Level 4문제 미로탈출이었다.

다익스트라 + 비트마스킹 문제였는데, 확실히 비트마스킹 문제에 내가 약하다는 것을 느꼈다.

항상 비트마스크 문제는 뭔가 다른 형태로 해결하려고하다가, 풀리지않아 답안을 확인하고 나서야 아 이런 형태로 풀수도있구나를 깨닫는 것 같다.

package Programmers;

import java.sql.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import org.w3c.dom.Node;

public class 미로탈출 {

    /*
        한쪽만 트랩이 활성화되어있는 경우 역방향
        양쪽 다 트랩이 활성화된 경우 정방향
     */
    static List<Node>[] list;
    static List<Node>[] rList;
    static Map<Integer, Integer> bitTrap;
    static int[][] dist;
    static final int INF = (int) 1e9;
    static int answer = INF;

    public static int solution(int n, int start, int end, int[][] roads, int[] traps) {
        list = new ArrayList[n + 1];
        rList = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
            rList[i] = new ArrayList<>();
        }

        for (int[] road : roads) {
            list[road[0]].add(new Node(road[1], road[2], 0));
            rList[road[1]].add(new Node(road[0], road[2], 0));
        }
        int idx = 1;
        bitTrap = new HashMap<>();
        for (int i = 0; i < traps.length; i++) {
            bitTrap.put(traps[i], 1 << (i + 1));
        }
        dist = new int[n + 1][1 << traps.length + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dist[i], INF);
        }

        dijk(start, end);
        for (int res : dist[end]) {
            answer = Math.min(res, answer);
        }
        return answer;
    }

    private static void dijk(int start, int end) {
        Queue<Node> que = new PriorityQueue<>();
        que.offer(new Node(start, 0, 0));
        dist[start][0] = 0;

        while (!que.isEmpty()) {
            Node n = que.poll();
            if (n.to == end) {
                break;
            }
            boolean fromActive = false;
            if (bitTrap.containsKey(n.to)) {
                if ((n.status & bitTrap.get(n.to)) == bitTrap.get(n.to)) {
                    fromActive = true;
                }
            }

            boolean toActive = false;
            for (Node next : list[n.to]) {
                int nStatus = n.status;
                if (bitTrap.containsKey(next.to)) {
                    toActive = ((n.status & bitTrap.get(next.to)) != 0);
                    nStatus = bitFlip(toActive, nStatus, bitTrap.get(next.to));

                    if (fromActive & toActive || (!fromActive & !toActive)) {
                        if (dist[next.to][n.status] > n.cost + next.cost) {
                            dist[next.to][n.status] = n.cost + next.cost;
                            que.offer(new Node(next.to, dist[next.to][n.status], nStatus));
                        }
                    }
                } else {
                    if (!fromActive) {
                        if (dist[next.to][n.status] > n.cost + next.cost) {
                            dist[next.to][n.status] = n.cost + next.cost;
                            que.offer(new Node(next.to, dist[next.to][n.status], nStatus));
                        }
                    }
                }
            }

            toActive = false;
            for (Node next : rList[n.to]) {
                int nStatus = n.status;
                if (bitTrap.containsKey(next.to)) {
                    toActive = ((n.status & bitTrap.get(next.to)) != 0);
                    nStatus = bitFlip(toActive, nStatus, bitTrap.get(next.to));

                }
                if (fromActive ^ toActive) {
                    if (dist[next.to][n.status] > n.cost + next.cost) {
                        dist[next.to][n.status] = n.cost + next.cost;
                        que.offer(new Node(next.to, dist[next.to][n.status], nStatus));
                    }
                }
            }


        }
    }

    private static int bitFlip(boolean flag, int now, int node) {
        // 다음 노드가 trap인데 활성화 되어있는 경우
        if (flag) {
            // 1110
            // 0010
            // 1100
            return now ^ node;
        }
        // 다음 노드가 trap인데 활성화 되어있지 않은 경우
        else {
            // 1100
            // 0010
            // 1110
            return now | node;
        }
    }

    static class Node implements Comparable<Node> {

        int to;
        int cost;
        int status;

        public Node(int to, int cost, int status) {
            this.to = to;
            this.cost = cost;
            this.status = status;
        }

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }


}

나중에 한번 꼭 다시 풀어봐야할 문제라고 생각한다.