add a solution for 841

fishercoder1534 · fishercoder1534 · commit ab123e99a3bc · 2021-11-02T15:36:47.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_841.java b/src/main/java/com/fishercoder/solutions/_841.java
@@ -58,4 +58,41 @@ public boolean canVisitAllRooms(List<List<Integer>> rooms) {
             return false;
         }
     }
+
+    public static class Solution3 {
+        /**
+         * My completely original recursive solution.
+         */
+        public boolean canVisitAllRooms(List<List<Integer>> rooms) {
+            Set<Integer> visited = new HashSet<>();
+            visited.add(0);
+            Set<Integer> keys = new HashSet<>();
+            keys.addAll(rooms.get(0));
+            return dfs(rooms, visited, keys);
+        }
+
+        private boolean dfs(List<List<Integer>> rooms, Set<Integer> visited, Set<Integer> keys) {
+            if (visited.size() == rooms.size()) {
+                return true;
+            }
+            Set<Integer> newKeys = new HashSet<>();
+            for (int key : keys) {
+                if (!visited.contains(key)) {
+                    visited.add(key);
+                    if (!rooms.get(key).isEmpty()) {
+                        newKeys.addAll(rooms.get(key));
+                    }
+                }
+            }
+            if (visited.size() == rooms.size()) {
+                return true;
+            }
+            if (newKeys.size() == 0) {
+                return false;
+            }
+            keys.addAll(newKeys);
+            dfs(rooms, visited, keys);
+            return visited.size() == rooms.size();
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_841Test.java b/src/test/java/com/fishercoder/_841Test.java
@@ -13,12 +13,14 @@
 public class _841Test {
     private static _841.Solution1 solution1;
     private static _841.Solution2 solution2;
+    private static _841.Solution3 solution3;
     private static List<List<Integer>> rooms;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _841.Solution1();
         solution2 = new _841.Solution2();
+        solution3 = new _841.Solution3();
     }
 
     @Test
@@ -30,6 +32,7 @@ public void test1() {
         rooms.add(Arrays.asList());
         assertEquals(true, solution1.canVisitAllRooms(rooms));
         assertEquals(true, solution2.canVisitAllRooms(rooms));
+        assertEquals(true, solution3.canVisitAllRooms(rooms));
     }
 
     @Test
@@ -41,5 +44,6 @@ public void test2() {
         rooms.add(Arrays.asList(0));
         assertEquals(false, solution1.canVisitAllRooms(rooms));
         assertEquals(false, solution2.canVisitAllRooms(rooms));
+        assertEquals(false, solution3.canVisitAllRooms(rooms));
     }
 }
