[리트코드] Medium 841. Keys and Rooms - 자바(JAVA)

문제 설명

n개의 방이 0번부터 n-1번까지 번호가 매겨져 있으며, 0번 방을 제외한 모든 방은 잠겨 있습니다. 당신의 목표는 모든 방을 방문하는 것입니다. 하지만, 열쇠 없이는 잠긴 방에 들어갈 수 없습니다.

 

방을 방문하면, 그 안에서 여러 개의 서로 다른 열쇠를 찾을 수 있습니다. 각 열쇠에는 해당 열쇠로 열 수 있는 방의 번호가 적혀 있으며, 이 열쇠들은 모두 가져갈 수 있습니다.

 

rooms라는 배열이 주어지고, rooms[i]는 i번 방을 방문했을 때 얻을 수 있는 열쇠들의 집합을 나타냅니다. 모든 방을 방문할 수 있다면 true를, 그렇지 않다면 false를 반환하세요.

 

 

제한사항

• n == rooms.length
• 2 <= n <= 1000
• 0 <= rooms[i].length <= 1000
• 1 <= sum(rooms[i].length) <= 3000
• 0 <= rooms[i][j] < n
• rooms[i]에 있는 값들은 모두 유일합니다.

---

문제 파악

• 0번 방에서 시작한다.
• 어떤 방 i의 열쇠를 가지면, rooms[i]를 통해 i번 방에 들어갈 수 있다.
• 모든 방에 방문할 수 있는지를 판별하는 문제이다.

 

접근 방법

• 0번 방에서 시작해서 DFS로 모든 방을 방문할 수 있는지 확인한다.
• 모든 방에 최소 한 번 방문할 수 있으면 true, 그렇지 않으면 false를 반환한다.
• 각 방을 하나의 노드로 보고, 열쇠로 갈 수 있는 방들을 엣지로 생각한다.

 

코드 구현

class Solution {
    public void dfs(List<List<Integer>> rooms, boolean[] visited, int curVertex) {
    	//현재 방 방문 처리
        visited[curVertex] = true;
        //현재 방에 있는 열쇠들 순회
        for (int nextVertex : rooms.get(curVertex)) {
        //아직 방문하지 않은 방 있으면 탐색
            if (!visited[nextVertex]) {
                dfs(rooms, visited, nextVertex);
            }
        }
    }

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] visited = new boolean[n];
        //0번 방부터 탐색
        dfs(rooms, visited, 0);
        
        //모든 방 방문했는지 확인
        for (int i=0; i<n; i++){
            if (!visited[i]) { //방문하지 않은 방 있으면 false 반환
                return false;
            } 
        }
        
        //모든 방 방문했으면 true 반환
        return true;
    }
}

• visited 배열을 만들어 방문한 방을 체크한다.
• dfs()를 통해 현재 방에서 갈 수 있는 모든 방을 방문한다.
• 마지막에 모든 방을 방문했는지 검사한다.

 

다른 풀이 / 피드백

정답 코드

1) BFS

//BFS
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
    //✅ 각 방의 방문 여부를 기록할 리스트를 선언한다.
        boolean[] visited = new boolean[rooms.size()];
        bfs(rooms, visited, 0);
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                return false;
            }
        }
        return true;
    }

    public void bfs(List<List<Integer>> rooms, boolean[] visited, int v) {
    //✅ 다음에 방문할 방을 기록할 큐를 선언한다.
        Queue<Integer> queue = new LinkedList<>();
        //✅ 큐에 시작 방(0)을 입력하고 방문 여부를 기록한다.
        visited[v] = true;
        queue.offer(v);
        //✅ 큐가 빌 때 까지 반복한다.
        while (!queue.isEmpty()) {
        //✅ 현재 방문한 방을 확인한다.
            int curVertex = queue.poll();
            //✅ 현재 방에 있는 열쇠를 확인한다.
            for (Integer nextVertex : rooms.get(curVertex)) {
            //✅ 열쇠가 갈 수 있는 방의 방문 여부를 확인한다.
                if (visited[nextVertex] == false) {
                //✅ 큐에 입력하고 방문 여부를 기록한다.
                    queue.offer(nextVertex);
                    visited[nextVertex] = true;
                }
            }
        }
    }
}

• 큐에 방문할 방을 추가하면서 순서대로 방문한다.

 

2) DFS

//DFS
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    static boolean[] visited;
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
    //✅ 각 방의 방문 여부를 기록할 리스트를 선언한다.
        visited = new boolean[rooms.size()];
        dfs(rooms, 0);

        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                return false;
            }
        }
        return true;
    }

//✅ dfs함수를 구현한다.
    public void dfs(List<List<Integer>> rooms, int v) {
    //✅ 현재 방문한 노드의 방문 여부를 기록한다.
        visited[v] = true;
        //✅ 현재 방에 있는 열쇠를 확인한다.
        for (Integer nextVertex : rooms.get(v)) {
        //✅ 열쇠가 갈 수 있는 방의 방문 여부를 확인한다.
            if (visited[nextVertex] == false) {
            //✅ 재귀함수를 호출한다.
                dfs(rooms, nextVertex);
            }
        }
    }
}

• visited 배열을 static으로 선언해 사용했다.

 

배운 점

• 문제를 '방'이나 '열쇠'처럼 추상적으로 주더라도, '노드와 엣지' 관점에서 보면 그래프로 풀 수 있다.