forked from ndb796/python-for-coding-test
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path8.py
More file actions
55 lines (53 loc) Β· 2.75 KB
/
8.py
File metadata and controls
55 lines (53 loc) Β· 2.75 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from collections import deque
def get_next_pos(pos, board):
next_pos = [] # λ°ν κ²°κ³Ό (μ΄λ κ°λ₯ν μμΉλ€)
pos = list(pos) # νμ¬ μμΉ μ 보λ₯Ό 리μ€νΈλ‘ λ³ν (μ§ν© β 리μ€νΈ)
pos1_x, pos1_y, pos2_x, pos2_y = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
# (μ, ν, μ’, μ°)λ‘ μ΄λνλ κ²½μ°μ λν΄μ μ²λ¦¬
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(4):
pos1_next_x, pos1_next_y, pos2_next_x, pos2_next_y = pos1_x + dx[i], pos1_y + dy[i], pos2_x + dx[i], pos2_y + dy[i]
# μ΄λνκ³ μ νλ λ μΉΈμ΄ λͺ¨λ λΉμ΄ μλ€λ©΄
if board[pos1_next_x][pos1_next_y] == 0 and board[pos2_next_x][pos2_next_y] == 0:
next_pos.append({(pos1_next_x, pos1_next_y), (pos2_next_x, pos2_next_y)})
# νμ¬ λ‘λ΄μ΄ κ°λ‘λ‘ λμ¬ μλ κ²½μ°
if pos1_x == pos2_x:
for i in [-1, 1]: # μμͺ½μΌλ‘ νμ νκ±°λ, μλμͺ½μΌλ‘ νμ
if board[pos1_x + i][pos1_y] == 0 and board[pos2_x + i][pos2_y] == 0: # μμͺ½ νΉμ μλμͺ½ λ μΉΈμ΄ λͺ¨λ λΉμ΄ μλ€λ©΄
next_pos.append({(pos1_x, pos1_y), (pos1_x + i, pos1_y)})
next_pos.append({(pos2_x, pos2_y), (pos2_x + i, pos2_y)})
# νμ¬ λ‘λ΄μ΄ μΈλ‘λ‘ λμ¬ μλ κ²½μ°
elif pos1_y == pos2_y:
for i in [-1, 1]: # μΌμͺ½μΌλ‘ νμ νκ±°λ, μ€λ₯Έμͺ½μΌλ‘ νμ
if board[pos1_x][pos1_y + i] == 0 and board[pos2_x][pos2_y + i] == 0: # μΌμͺ½ νΉμ μ€λ₯Έμͺ½ λ μΉΈμ΄ λͺ¨λ λΉμ΄ μλ€λ©΄
next_pos.append({(pos1_x, pos1_y), (pos1_x, pos1_y + i)})
next_pos.append({(pos2_x, pos2_y), (pos2_x, pos2_y + i)})
# νμ¬ μμΉμμ μ΄λν μ μλ μμΉλ₯Ό λ°ν
return next_pos
def solution(board):
# λ§΅μ μΈκ³½μ λ²½μ λλ ννλ‘ λ§΅ λ³ν
n = len(board)
new_board = [[1] * (n + 2) for _ in range(n + 2)]
for i in range(n):
for j in range(n):
new_board[i + 1][j + 1] = board[i][j]
# λλΉ μ°μ νμ(BFS) μν
q = deque()
visited = []
pos = {(1, 1), (1, 2)} # μμ μμΉ μ€μ
q.append((pos, 0)) # νμ μ½μ
ν λ€μ
visited.append(pos) # λ°©λ¬Έ μ²λ¦¬
# νκ° λΉ λκΉμ§ λ°λ³΅
while q:
pos, cost = q.popleft()
# (n, n) μμΉμ λ‘λ΄μ΄ λλ¬νλ€λ©΄, μ΅λ¨ 거리μ΄λ―λ‘ λ°ν
if (n, n) in pos:
return cost
# νμ¬ μμΉμμ μ΄λν μ μλ μμΉ νμΈ
for next_pos in get_next_pos(pos, new_board):
# μμ§ λ°©λ¬Ένμ§ μμ μμΉλΌλ©΄ νμ μ½μ
νκ³ λ°©λ¬Έ μ²λ¦¬
if next_pos not in visited:
q.append((next_pos, cost + 1))
visited.append(next_pos)
return 0