1941 solve

alsrl8 · alsrl8 · commit a26e60cf7ef6 · 2022-10-19T16:32:36.000+09:00
칠공주가 가로로 나란히 있을 거라고 잘못 가정해서 많이 틀림
diff --git a/2022/[Week27 - Mix]/송민기/1941.py b/2022/[Week27 - Mix]/송민기/1941.py
@@ -0,0 +1,31 @@
+from itertools import combinations
+from collections import deque
+
+grid = [input().rstrip() for _ in range(5)]
+arr = [(r, c) for r in range(5) for c in range(5)]
+comb = list(combinations(arr, 7))  # 480700
+dRow, dCol = [0, 0, 1, -1], [1, -1, 0, 0]
+
+answer = 0
+for _comb in comb:
+    cnt_s = 0
+    for r, c in _comb:
+        if grid[r][c] == 'S':
+            cnt_s += 1
+    if cnt_s < 4:
+        continue
+    r, c = _comb[0]
+    q = deque()
+    q.append((r, c))
+    visited = set()
+    visited.add((r, c))
+    while q:
+        _r, _c = q.popleft()
+        for d in range(4):
+            nr, nc = _r + dRow[d], _c + dCol[d]
+            if (nr, nc) in _comb and (nr, nc) not in visited:
+                q.append((nr, nc))
+                visited.add((nr, nc))
+    if len(visited) == 7:
+        answer += 1
+print(answer)
