DevOnPlayStudy · dldydtjs2965 · Sep 28, 2024 · Sep 11, 2024
diff --git a/w12/yjkwon/30_150365.py b/w12/yjkwon/30_150365.py
@@ -0,0 +1,43 @@
+# 미로 탈출 명령어
+
+"""
+백트래킹 기법을 사용합니다
+
+1. 기존 결과보다 현재의 경로가 사전 순으로 더 뒤에 오면 탐색을 종료합니다
+2. 남은 k가 없는데, 종료지점에 도달하지 못한 경우 탐색을 종료합니다
+3. 남은 거리가 k보다 크면 탐색을 종료합니다
+4. 남은 거리가 짝수인데 k가 홀수이면 탐색을 종료합니다
+"""
+
+import sys
+
+sys.setrecursionlimit(5000)
+
+
+def solution(n, m, x, y, r, c, k):
+    xarr = [1, 0, 0, -1]
+    yarr = [0, -1, 1, 0]
+    commands = "dlru"
+    result = ["z" * k]
+
+    def backtrack(x, y, k, path):
+        if result[0] <= path:
+            return
+        if x == r and y == c and k == 0:
+            result[0] = path
+            return
+        if k == 0:
+            return
+        remain = abs(x - r) + abs(y - c)
+        if remain > k:
+            return
+        if not (remain % 2) and k % 2:
+            return
+
+        for i in range(4):
+            nx, ny = x + xarr[i], y + yarr[i]
+            if 1 <= nx <= n and 1 <= ny <= m:
+                backtrack(nx, ny, k - 1, path + commands[i])
+
+    backtrack(x, y, k, "")
+    return result[0] if "z" not in result[0] else "impossible"
diff --git a/w12/yjkwon/30_154540.py b/w12/yjkwon/30_154540.py
@@ -0,0 +1,47 @@
+# 무인도 여행
+
+"""
+1. 탐색의 출발점이 될 수 있는 지점을 모두 구합니다
+2. 지점이 하나도 없으면 [-1]을 리턴합니다
+3. 지점마다 순회하며 값을 셉니다
+"""
+
+
+from collections import deque
+
+
+def solution(maps):
+    points = []
+    for i, row in enumerate(maps):
+        for j, v in enumerate(row):
+            if v.isnumeric():
+                points.append((i, j))
+    if not points:
+        return [-1]
+
+    n, m = len(maps), len(maps[0])
+    answers = []
+    visited = set()
+    for x, y in points:
+        if (x, y) in visited:
+            continue
+        stack = deque([(x, y)])
+        visited.add((x, y))
+        answer = 0
+        while stack:
+            x, y = stack.pop()
+            answer += int(maps[x][y])
+
+            for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
+                xp, yp = x + dx, y + dy
+                if (
+                    0 <= xp < n
+                    and 0 <= yp < m
+                    and (xp, yp) not in visited
+                    and maps[xp][yp] != "X"
+                ):
+                    stack.append((xp, yp))
+                    visited.add((xp, yp))
+        answers.append(answer)
+    answers.sort()
+    return answers
diff --git a/w12/yjkwon/30_159993.py b/w12/yjkwon/30_159993.py
@@ -0,0 +1,50 @@
+# 미로 탈출
+
+"""
+시작지점 -> 레버
+레버 -> 종료지점
+순서로 bfs 탐색을 하며 소요시간을 구합니다
+"""
+
+from collections import deque
+
+
+def solution(maps):
+    start = ()
+    lever = ()
+    exit = ()
+    for i, row in enumerate(maps):
+        for j, v in enumerate(row):
+            if v == "S":
+                start = (i, j)
+            elif v == "L":
+                lever = (i, j)
+            elif v == "E":
+                exit = (i, j)
+
+    def bfs(n, m, start, goal):
+        queue = deque([(0, *start)])
+        visited = set([start])
+        while queue:
+            c, x, y = queue.popleft()
+            if (x, y) == goal:
+                return c
+
+            for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
+                nx, ny = x + dx, y + dy
+                if (
+                    0 <= nx < n
+                    and 0 <= ny < m
+                    and maps[nx][ny] != "X"
+                    and (nx, ny) not in visited
+                ):
+                    queue.append((c + 1, nx, ny))
+                    visited.add((nx, ny))
+        return -1
+
+    n, m = len(maps), len(maps[0])
+    c1 = bfs(n, m, start, lever)
+    c2 = bfs(n, m, lever, exit)
+    if c1 == -1 or c2 == -1:
+        return -1
+    return c1 + c2
diff --git a/w12/yjkwon/30_172927.py b/w12/yjkwon/30_172927.py
@@ -0,0 +1,54 @@
+# 광물 캐기
+
+"""
+1. 주어진 광물들을 5개씩 분리합니다
+2. 광물들을 가치가 높은 순서로 정렬합니다
+3. 분리된 광물들을 가치가 높은 곡괭이 순서로 캡니다
+"""
+
+
+def custom_key(ms):
+    d = ms.count("diamond")
+    i = ms.count("iron")
+    s = ms.count("stone")
+    return d * 25 + i * 5 + s
+
+
+def solution(picks, minerals):
+    sliced = []
+    for i in range(0, min(len(minerals), sum(picks) * 5), 5):
+        ms = minerals[i : i + 5]
+        sliced.append(ms)
+    sliced.sort(key=custom_key, reverse=True)
+
+    answer = 0
+
+    def mine(ms):
+        count = 0
+        p = None
+        for i in range(3):
+            if picks[i] > 0:
+                picks[i] -= 1
+                p = i
+                break
+        for m in ms:
+            if p == 0:
+                count += 1
+            elif p == 1:
+                if m == "diamond":
+                    count += 5
+                else:
+                    count += 1
+            else:
+                if m == "diamond":
+                    count += 25
+                elif m == "iron":
+                    count += 5
+                else:
+                    count += 1
+        return count
+
+    for ms in sliced:
+        answer += mine(ms)
+
+    return answer
diff --git a/w12/yjkwon/30_86971.py b/w12/yjkwon/30_86971.py
@@ -0,0 +1,44 @@
+# 전력망을 둘로 나누기
+
+"""
+1. 주어진 연결을 이용해 트리를 만듭니다.
+2. 각 연결별로 순회하며 연결 종단의 두 노드를 시작으로 연결된 노드의 갯수를 셉니다
+"""
+
+from collections import deque
+
+
+class Node:
+    def __init__(self):
+        self.connected = list()
+
+
+def solution(n, wires):
+    tree = dict()
+
+    def extend_tree(x, y):
+        if x not in tree:
+            tree[x] = Node()
+        tree[x].connected.append(y)
+
+    for x, y in wires:
+        extend_tree(x, y)
+        extend_tree(y, x)
+
+    def count_nodes(x, y):
+        visited = set([x, y])
+        queue = deque([x])
+        count = 0
+        while queue:
+            v = queue.popleft()
+            visited.add(v)
+            count += 1
+            queue.extend([n for n in tree[v].connected if n not in visited])
+        return count
+
+    answers = []
+    for x, y in wires:
+        answers.append((count_nodes(x, y), count_nodes(y, x)))
+
+    answers.sort(key=lambda x: abs(x[0] - x[1]))
+    return abs(answers[0][0] - answers[0][1])