-
Notifications
You must be signed in to change notification settings - Fork 0
/
무인도 여행.py
67 lines (50 loc) · 1.36 KB
/
무인도 여행.py
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
"""
시작 시간: 2023-02-02 01:57 PM
소요 시간: 20분
풀이 방법: dfs인데 맵에 직접 표시 안하고 visited에 표시했으면 더 좋았을 듯
"""
def get_map_array_style(map):
array_style_map = []
for line in map:
new_line = []
for char in line:
if char != 'X':
char = int(char)
new_line.append(char)
array_style_map.append(new_line)
return array_style_map
def is_valid_position(x, y):
global MAP
if not (0 <= x < len(MAP) and 0 <= y < len(MAP[0])):
return False
return True
def dfs(x, y):
global MAP
food = 0
stack = [(x, y)]
diffs = ((-1, 0), (1, 0), (0, 1), (0, -1))
while stack:
x, y = stack.pop()
if not is_valid_position(x, y):
continue
if MAP[x][y] == 'X':
continue
food += MAP[x][y]
MAP[x][y] = 'X'
for dx, dy in diffs:
stack.append((x+dx, y+dy))
return food
def solution(maps):
global MAP
MAP = get_map_array_style(maps)
answer = []
for i in range(len(MAP)):
for j in range(len(MAP[0])):
food = dfs(i, j)
if food > 0:
answer.append(food)
if len(answer) == 0:
return [-1]
answer.sort()
return answer
print(solution(["X591X","X1X5X","X231X", "1XXX1"]))