841. Keys and Rooms #

Problem #

There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0).

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

Input: [[1],[2],[3],[]]
Output: true
Explanation:  
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.

Example 2:

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.

Note:

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
The number of keys in all rooms combined is at most 3000.

Problem Summary #

There are N rooms, and initially you are in room 0. Each room has a different number: 0, 1, 2, …, N-1, and there may be some keys in the rooms that allow you to enter the next room.

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is represented by an integer in [0,1, …, N-1], where N = rooms.length. The key rooms[i][j] = v can open the room numbered v. Initially, all rooms except room 0 are locked. You can freely walk back and forth between rooms. Return true if you can enter every room; otherwise return false.

Notes:

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
The total number of keys in all rooms does not exceed 3000.

Solution Approach #

Given an array of rooms, each room contains some keys. Room 0 can be entered by default, and there is no requirement on the order in which rooms are entered. Determine whether all rooms can eventually be entered.
Use DFS to search through the keys of all rooms in sequence. If all rooms can be visited, finally output true. This problem is considered an easy DFS problem.

Code #

func canVisitAllRooms(rooms [][]int) bool {
	visited := make(map[int]bool)
	visited[0] = true
	dfsVisitAllRooms(rooms, visited, 0)
	return len(rooms) == len(visited)
}

func dfsVisitAllRooms(es [][]int, visited map[int]bool, from int) {
	for _, to := range es[from] {
		if visited[to] {
			continue
		}
		visited[to] = true
		dfsVisitAllRooms(es, visited, to)
	}
}