forked from ndb796/python-for-coding-test
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path2.py
More file actions
89 lines (76 loc) ยท 3.49 KB
/
2.py
File metadata and controls
89 lines (76 loc) ยท 3.49 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import copy
# 4 X 4 ํฌ๊ธฐ ๊ฒฉ์์ ์กด์ฌํ๋ ๊ฐ ๋ฌผ๊ณ ๊ธฐ์ ๋ฒํธ(์์ผ๋ฉด -1)์ ๋ฐฉํฅ ๊ฐ์ ๋ด๋ ํ
์ด๋ธ
array = [[None] * 4 for _ in range(4)]
for i in range(4):
data = list(map(int, input().split()))
# ๋งค ์ค๋ง๋ค 4๋ง๋ฆฌ์ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ํ๋์ฉ ํ์ธํ๋ฉฐ
for j in range(4):
# ๊ฐ ์์น๋ง๋ค [๋ฌผ๊ณ ๊ธฐ์ ๋ฒํธ, ๋ฐฉํฅ]์ ์ ์ฅ
array[i][j] = [data[j * 2], data[j * 2 + 1] - 1]
# 8๊ฐ์ง ๋ฐฉํฅ์ ๋ํ ์ ์
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]
# ํ์ฌ ์์น์์ ์ผ์ชฝ์ผ๋ก ํ์ ๋ ๊ฒฐ๊ณผ ๋ฐํ
def turn_left(direction):
return (direction + 1) % 8
result = 0 # ์ต์ข
๊ฒฐ๊ณผ
# ํ์ฌ ๋ฐฐ์ด์์ ํน์ ํ ๋ฒํธ์ ๋ฌผ๊ณ ๊ธฐ ์์น ์ฐพ๊ธฐ
def find_fish(array, index):
for i in range(4):
for j in range(4):
if array[i][j][0] == index:
return (i, j)
return None
# ๋ชจ๋ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ํ์ ๋ฐ ์ด๋์ํค๋ ํจ์
def move_all_fishes(array, now_x, now_y):
# 1๋ฒ๋ถํฐ 16๋ฒ๊น์ง์ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ์ฐจ๋ก๋๋ก (๋ฎ์ ๋ฒํธ๋ถํฐ) ํ์ธ
for i in range(1, 17):
# ํด๋น ๋ฌผ๊ณ ๊ธฐ์ ์์น๋ฅผ ์ฐพ๊ธฐ
position = find_fish(array, i)
if position != None:
x, y = position[0], position[1]
direction = array[x][y][1]
# ํด๋น ๋ฌผ๊ณ ๊ธฐ์ ๋ฐฉํฅ์ ์ผ์ชฝ์ผ๋ก ๊ณ์ ํ์ ์ํค๋ฉฐ ์ด๋์ด ๊ฐ๋ฅํ์ง ํ์ธ
for j in range(8):
nx = x + dx[direction]
ny = y + dy[direction]
# ํด๋น ๋ฐฉํฅ์ผ๋ก ์ด๋์ด ๊ฐ๋ฅํ๋ค๋ฉด ์ด๋ ์ํค๊ธฐ
if 0 <= nx and nx < 4 and 0 <= ny and ny < 4:
if not (nx == now_x and ny == now_y):
array[x][y][1] = direction
array[x][y], array[nx][ny] = array[nx][ny], array[x][y]
break
direction = turn_left(direction)
# ์์ด๊ฐ ํ์ฌ ์์น์์ ๋จน์ ์ ์๋ ๋ชจ๋ ๋ฌผ๊ณ ๊ธฐ์ ์์น ๋ฐํ
def get_possible_positions(array, now_x, now_y):
positions = []
direction = array[now_x][now_y][1]
# ํ์ฌ์ ๋ฐฉํฅ์ผ๋ก ์ญ ์ด๋ํ๊ธฐ
for i in range(4):
now_x += dx[direction]
now_y += dy[direction]
# ๋ฒ์๋ฅผ ๋ฒ์ด๋์ง ์๋์ง ํ์ธํ๋ฉฐ
if 0 <= now_x and now_x < 4 and 0 <= now_y and now_y < 4:
# ๋ฌผ๊ณ ๊ธฐ๊ฐ ์กด์ฌํ๋ ๊ฒฝ์ฐ
if array[now_x][now_y][0] != -1:
positions.append((now_x, now_y))
return positions
# ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ํ์ํ๊ธฐ ์ํ DFS ํจ์
def dfs(array, now_x, now_y, total):
global result
array = copy.deepcopy(array) # ๋ฆฌ์คํธ๋ฅผ ํต์งธ๋ก ๋ณต์ฌ
total += array[now_x][now_y][0] # ํ์ฌ ์์น์ ๋ฌผ๊ณ ๊ธฐ ๋จน๊ธฐ
array[now_x][now_y][0] = -1 # ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน์์ผ๋ฏ๋ก ๋ฒํธ ๊ฐ์ -1๋ก ๋ณํ
move_all_fishes(array, now_x, now_y) # ์ ์ฒด ๋ฌผ๊ณ ๊ธฐ ์ด๋ ์ํค๊ธฐ
# ์ด์ ๋ค์ ์์ด๊ฐ ์ด๋ํ ์ฐจ๋ก์ด๋ฏ๋ก, ์ด๋ ๊ฐ๋ฅํ ์์น ์ฐพ๊ธฐ
positions = get_possible_positions(array, now_x, now_y)
# ์ด๋ํ ์ ์๋ ์์น๊ฐ ํ๋๋ ์๋ค๋ฉด ์ข
๋ฃ
if len(positions) == 0:
result = max(result, total) # ์ต๋๊ฐ ์ ์ฅ
return
# ๋ชจ๋ ์ด๋ํ ์ ์๋ ์์น๋ก ์ฌ๊ท์ ์ผ๋ก ์ํ
for next_x, next_y in positions:
dfs(array, next_x, next_y, total)
# ์ฒญ์๋
์์ด์ ์์ ์์น(0, 0)์์๋ถํฐ ์ฌ๊ท์ ์ผ๋ก ๋ชจ๋ ๊ฒฝ์ฐ ํ์
dfs(array, 0, 0, 0)
print(result)