[LeetCode] 841. Keys and Rooms

[문제 링크]

https://leetcode.com/problems/keys-and-rooms/description/

 

[문제]

당신은 n개의 방(0번부터 n-1번까지 번호가 매겨짐)으로 이루어진 건물에 있다.

처음에는 0번 방에 있으며, 이 방은 열려 있다. 나머지 방들은 모두 잠겨 있다. 각 방에는 일부 다른 방의 열쇠들이 들어 있을 수 있다. 열쇠를 이용해 해당 방을 열고 들어갈 수 있다.

모든 방을 방문할 수 있는지 확인하라.

모든 방을 방문할 수 있으면 true, 그렇지 않으면 false를 반환한다.

[풀이 과정]

문제를 보니 출발점 하나를 잡고 깊게 쭉 조사하는게 효과적일 것 같아

DFS로 구현하기로하고 구현했다.

 

[코드]

class Solution {
    int x;
    List<List<Integer>> rooms;
    boolean[] visited;

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        this.x = rooms.size();
        this.rooms = rooms;
        this.visited = new boolean[x];

        // 0번방에서 DFS 시작
        dfs(0);

        // 하나도 빠짐없이 방문했는지 검색
        for(boolean visit : visited) {
            if(!visit) {
                return false;
            }
        }

        return true;
    }

    public void dfs(int room) {
        visited[room] = true;

        for(int key : rooms.get(room)) {
            if(!visited[key]) {
                dfs(key);
            }
        }
    }
}

[회고]

쉬웠습니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.