da-in · da-in · Mar 5, 2023 · Mar 1, 2023 · Mar 1, 2023 · Mar 2, 2023
diff --git a/Programmers - 고득점 Kit/[DFS-BFS] 네트워크/dain.py b/Programmers - 고득점 Kit/[DFS-BFS] 네트워크/dain.py
@@ -0,0 +1,19 @@
+from collections import deque
+
+def solution(n, computers):
+    answer = set()
+    for i in range(n):
+        visit = [0 for _ in range(n)]
+        q = deque([i])
+        visit[i] = 1
+        root = i
+        while q:
+            cur = q.popleft()
+            root = min(cur, root)
+            for j in range(n):
+                if computers[cur][j] == 1 and visit[j] == 0:
+                    q.append(j)
+                    visit[j] = 1
+        answer.add(root)
+
+    return len(answer)
diff --git a/Programmers - 고득점 Kit/[그래프] 방의 개수/dain.py b/Programmers - 고득점 Kit/[그래프] 방의 개수/dain.py
@@ -0,0 +1,55 @@
+def solution(arrows):
+    answer = 0
+    graph = {(0, 0): set()}
+    dx = [0, 1, 1, 1, 0, -1, -1, -1]
+    dy = [1, 1, 0, -1, -1, -1, 0, 1]
+    x = y = nx = ny = 0
+
+    def isCross(a, x, y):
+        if a == 1 and (x, y + 1) in graph.keys() and (x + 1, y) in graph[(x, y + 1)]:
+            return True
+        elif a == 3 and (x, y - 1) in graph.keys() and (x + 1, y) in graph[(x, y - 1)]:
+            return True
+        elif a == 5 and (x, y - 1) in graph.keys() and (x - 1, y) in graph[(x, y - 1)]:
+            return True
+        elif a == 7 and (x, y + 1) in graph.keys() and (x - 1, y) in graph[(x, y + 1)]:
+            return True
+        return False
+
+    for a in arrows:
+        nx = x + dx[a]
+        ny = y + dy[a]
+        graph[(x, y)].add((nx, ny))
+        if (nx, ny) in graph.keys():
+            if (x, y) not in graph[(nx, ny)]:
+                graph[(nx, ny)].add((x, y))
+                answer += 1
+                if isCross(a, x, y):
+                    answer += 1
+        else:
+            graph[(nx, ny)] = {(x, y)}
+            if isCross(a, x, y):
+                answer += 1
+        x, y = nx, ny
+    return answer
+
+
+# 오일러 정리를 이용한 코드
+# v-e+f = 1
+# v: 꼭짓점, e:모서리, f:면
+
+def solution(arrows):
+    # f = 1 + e - v
+    e = set()
+    v = {(0, 0)}
+    dx = [0, 1, 1, 1, 0, -1, -1, -1]
+    dy = [1, 1, 0, -1, -1, -1, 0, 1]
+    x = y = nx = ny = 0
+    for a in arrows:
+        for _ in range(2):
+            nx = x + dx[a]
+            ny = y + dy[a]
+            v.add((nx, ny))
+            e.add(frozenset({(nx, ny), (x, y)}))
+            x, y = nx, ny
+    return 1 + len(e) - len(v)
diff --git a/Programmers - 고득점 Kit/[해시] 베스트앨범/dain.py b/Programmers - 고득점 Kit/[해시] 베스트앨범/dain.py
@@ -0,0 +1,20 @@
+from collections import defaultdict
+
+
+def solution(genres, plays):
+    genreCount = defaultdict(int)
+    genrePlay = defaultdict(list)
+    answer = []
+    for i in range(len(genres)):
+        genreCount[genres[i]] += plays[i]
+        genrePlay[genres[i]].append((plays[i], i))
+
+    genreCount = sorted(genreCount.items(), key=lambda item: item[1], reverse=True)
+
+    for genre, _ in genreCount:
+        genrePlay[genre].sort(key=lambda x: (-x[0], x[1]))
+        top2 = genrePlay[genre][0:2]
+        for p in top2:
+            answer.append(p[1])
+
+    return answer