[LeetCode] 847 - Shortest Path Visiting All Nodes(java)

https://leetcode.com/problems/shortest-path-visiting-all-nodes/?envType=daily-question&envId=2023-09-17 

LeetCode - The World's Leading Online Programming Learning Platform

최단경로를 찾는 문제이다. 즉 bfs를 활용하여 풀 수 있다.

 

핵심

최단경로를 찾는 문제이지만, 방문한 곳을 다시 갈 수 있다.

중요한 점은 갔던 길을 계속해서 반복할 여지가 있다.(무한 루프)

이를 해결해줘야 한다.

 

정답 코드 

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int allVisited = (1 << n) - 1;
        Set<Integer> visited = new HashSet<>();

        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            q.offer(new int[]{1 << i, i, 0});
            visited.add((1 << i) * 16 + i);
        }

        while (!q.isEmpty()) {
            int[] now = q.poll();

            if (now[0] == allVisited) {
                return now[2];
            }

            for (int next : graph[now[1]]) {
                int mask = now[0] | (1 << next);
                int value = mask * 16 + next;

                if (!visited.contains(value)) {
                    visited.add(value);
                    q.offer(new int[]{mask, next, now[2] + 1});
                }
            }
        }

        return -1;
    }
}

해설

우선 비트마스크를 사용하여 전체 탐색여부를 체크했다.

ex) 0001(2) -> 첫 번째 노드만 방문

이후 중요한 점은 visited이다.

무한루프를 방지하기 위해 재방문은 허용하지만 재재방문은 허용하지 않음

즉 1->2, 2->1 갈 수 있지만 이후에 다시 1->2는 탐색하지 않게 하기 위해 사용하였다.

특정 노드에서 다른 노드로 갈 때 고윳값을 set에 저장하여 방문 기록이 있으면 탐색하지 않음

또한 시작점에 따라 최단기록이 달라질 수 있기에 0~n-1번째 노드를 전부 넣어준다.

 

배운 점

우선 비트마스크가 익숙하지 않아서 아이디어 자체를 떠올리기 힘들었다.

또한 처음에 set 말고 list를 사용하였는데 contains부분 때문에 시간초과가 발생했다.

list의 contains는 O(n)이지만, set의 contains는 O(1) 이기 때문이다.

작은 차이라도 시간을 줄일 수 있는 방법을 사용하고 의식하자