Skip to content

Commit b736d6a

Browse files
dldydtjs2965dldydtjs2965
authored
Merge pull request DevOnPlayStudy#27 from youngjaekwon/yjkwon/week12
yjkwon: add solution w12
2 parents 84e319e + 80f1539 commit b736d6a

5 files changed

Lines changed: 238 additions & 0 deletions

File tree

‎w12/yjkwon/30_150365.py‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
# 미로 탈출 명령어
2+
3+
"""
4+
백트래킹 기법을 사용합니다
5+
6+
1. 기존 결과보다 현재의 경로가 사전 순으로 더 뒤에 오면 탐색을 종료합니다
7+
2. 남은 k가 없는데, 종료지점에 도달하지 못한 경우 탐색을 종료합니다
8+
3. 남은 거리가 k보다 크면 탐색을 종료합니다
9+
4. 남은 거리가 짝수인데 k가 홀수이면 탐색을 종료합니다
10+
"""
11+
12+
import sys
13+
14+
sys.setrecursionlimit(5000)
15+
16+
17+
def solution(n, m, x, y, r, c, k):
18+
xarr = [1, 0, 0, -1]
19+
yarr = [0, -1, 1, 0]
20+
commands = "dlru"
21+
result = ["z" * k]
22+
23+
def backtrack(x, y, k, path):
24+
if result[0] <= path:
25+
return
26+
if x == r and y == c and k == 0:
27+
result[0] = path
28+
return
29+
if k == 0:
30+
return
31+
remain = abs(x - r) + abs(y - c)
32+
if remain > k:
33+
return
34+
if not (remain % 2) and k % 2:
35+
return
36+
37+
for i in range(4):
38+
nx, ny = x + xarr[i], y + yarr[i]
39+
if 1 <= nx <= n and 1 <= ny <= m:
40+
backtrack(nx, ny, k - 1, path + commands[i])
41+
42+
backtrack(x, y, k, "")
43+
return result[0] if "z" not in result[0] else "impossible"

‎w12/yjkwon/30_154540.py‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
# 무인도 여행
2+
3+
"""
4+
1. 탐색의 출발점이 될 수 있는 지점을 모두 구합니다
5+
2. 지점이 하나도 없으면 [-1]을 리턴합니다
6+
3. 지점마다 순회하며 값을 셉니다
7+
"""
8+
9+
10+
from collections import deque
11+
12+
13+
def solution(maps):
14+
points = []
15+
for i, row in enumerate(maps):
16+
for j, v in enumerate(row):
17+
if v.isnumeric():
18+
points.append((i, j))
19+
if not points:
20+
return [-1]
21+
22+
n, m = len(maps), len(maps[0])
23+
answers = []
24+
visited = set()
25+
for x, y in points:
26+
if (x, y) in visited:
27+
continue
28+
stack = deque([(x, y)])
29+
visited.add((x, y))
30+
answer = 0
31+
while stack:
32+
x, y = stack.pop()
33+
answer += int(maps[x][y])
34+
35+
for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
36+
xp, yp = x + dx, y + dy
37+
if (
38+
0 <= xp < n
39+
and 0 <= yp < m
40+
and (xp, yp) not in visited
41+
and maps[xp][yp] != "X"
42+
):
43+
stack.append((xp, yp))
44+
visited.add((xp, yp))
45+
answers.append(answer)
46+
answers.sort()
47+
return answers

‎w12/yjkwon/30_159993.py‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
# 미로 탈출
2+
3+
"""
4+
시작지점 -> 레버
5+
레버 -> 종료지점
6+
순서로 bfs 탐색을 하며 소요시간을 구합니다
7+
"""
8+
9+
from collections import deque
10+
11+
12+
def solution(maps):
13+
start = ()
14+
lever = ()
15+
exit = ()
16+
for i, row in enumerate(maps):
17+
for j, v in enumerate(row):
18+
if v == "S":
19+
start = (i, j)
20+
elif v == "L":
21+
lever = (i, j)
22+
elif v == "E":
23+
exit = (i, j)
24+
25+
def bfs(n, m, start, goal):
26+
queue = deque([(0, *start)])
27+
visited = set([start])
28+
while queue:
29+
c, x, y = queue.popleft()
30+
if (x, y) == goal:
31+
return c
32+
33+
for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
34+
nx, ny = x + dx, y + dy
35+
if (
36+
0 <= nx < n
37+
and 0 <= ny < m
38+
and maps[nx][ny] != "X"
39+
and (nx, ny) not in visited
40+
):
41+
queue.append((c + 1, nx, ny))
42+
visited.add((nx, ny))
43+
return -1
44+
45+
n, m = len(maps), len(maps[0])
46+
c1 = bfs(n, m, start, lever)
47+
c2 = bfs(n, m, lever, exit)
48+
if c1 == -1 or c2 == -1:
49+
return -1
50+
return c1 + c2

‎w12/yjkwon/30_172927.py‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
# 광물 캐기
2+
3+
"""
4+
1. 주어진 광물들을 5개씩 분리합니다
5+
2. 광물들을 가치가 높은 순서로 정렬합니다
6+
3. 분리된 광물들을 가치가 높은 곡괭이 순서로 캡니다
7+
"""
8+
9+
10+
def custom_key(ms):
11+
d = ms.count("diamond")
12+
i = ms.count("iron")
13+
s = ms.count("stone")
14+
return d * 25 + i * 5 + s
15+
16+
17+
def solution(picks, minerals):
18+
sliced = []
19+
for i in range(0, min(len(minerals), sum(picks) * 5), 5):
20+
ms = minerals[i : i + 5]
21+
sliced.append(ms)
22+
sliced.sort(key=custom_key, reverse=True)
23+
24+
answer = 0
25+
26+
def mine(ms):
27+
count = 0
28+
p = None
29+
for i in range(3):
30+
if picks[i] > 0:
31+
picks[i] -= 1
32+
p = i
33+
break
34+
for m in ms:
35+
if p == 0:
36+
count += 1
37+
elif p == 1:
38+
if m == "diamond":
39+
count += 5
40+
else:
41+
count += 1
42+
else:
43+
if m == "diamond":
44+
count += 25
45+
elif m == "iron":
46+
count += 5
47+
else:
48+
count += 1
49+
return count
50+
51+
for ms in sliced:
52+
answer += mine(ms)
53+
54+
return answer

‎w12/yjkwon/30_86971.py‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
# 전력망을 둘로 나누기
2+
3+
"""
4+
1. 주어진 연결을 이용해 트리를 만듭니다.
5+
2. 각 연결별로 순회하며 연결 종단의 두 노드를 시작으로 연결된 노드의 갯수를 셉니다
6+
"""
7+
8+
from collections import deque
9+
10+
11+
class Node:
12+
def __init__(self):
13+
self.connected = list()
14+
15+
16+
def solution(n, wires):
17+
tree = dict()
18+
19+
def extend_tree(x, y):
20+
if x not in tree:
21+
tree[x] = Node()
22+
tree[x].connected.append(y)
23+
24+
for x, y in wires:
25+
extend_tree(x, y)
26+
extend_tree(y, x)
27+
28+
def count_nodes(x, y):
29+
visited = set([x, y])
30+
queue = deque([x])
31+
count = 0
32+
while queue:
33+
v = queue.popleft()
34+
visited.add(v)
35+
count += 1
36+
queue.extend([n for n in tree[v].connected if n not in visited])
37+
return count
38+
39+
answers = []
40+
for x, y in wires:
41+
answers.append((count_nodes(x, y), count_nodes(y, x)))
42+
43+
answers.sort(key=lambda x: abs(x[0] - x[1]))
44+
return abs(answers[0][0] - answers[0][1])

0 commit comments

Comments
 (0)