19236. 청소년 상어 문제 바로가기
해결 방법
기본 설정
4행 4열의 리스트인 ocean을 다음과 같이 각 칸에 물고기의 번호와 방향을 저장!
즉 문제에서 제시된 표를 그림과 같이 [상어의 크기, 방향]으로 ocean에 저장한다.
상어에 대한 정보는 sh_y, sh_x, sh_d 변수에 저장한다.
ocean에 상어의 위치를 [-1, -1]로 표시한다.
이후 shark 함수를 동작시킨다.
shark 함수
shark 함수 안에 move_fish 함수를 넣어 물고기를 이동시킨 뒤 상어가 움질일 수 있도록 한다.
상어를 상어의 이동 방향으로 이동시키며 물고기가 있는 경우를 eat_list에 저장한다.
eat_list에 하나씩 경우를 deepcopy를 통해 완전 탐색한다.
eat_list가 없을 경우 상어의 이동이 끝나는 집으로 돌아가는 단계이므로 final_eat(출력할값, 정답)과 비교하여 큰 경우를 구해준다.
move_fish 함수
작은 번호부터 이동시키는 것으로 1번부터 16번까지 하나씩 이동시킨다.
번호를 가진 물고기를 찾으면 이동 가능한 위치인 경우(ocean 공간안에 있으며 상어 위치가 아닌 경우) 이동하고 그렇지 않은 경우 방향을 바꿔주도록 설정한다.
1 2 3 4 5 6 7 8 9 10
if [y, x, d] != [-1, -1, -1]: # 초기화 값과 다르기에 물고기 찾음!! for _ in range(8): ny, nx = y + dirs[d][0], x + dirs[d][1] if 0 <= ny < 4 and 0 <= nx < 4 and ocean[ny][nx][0] != -1: ocean[ny][nx], ocean[y][x] = ocean[y][x], ocean[ny][nx] ocean[ny][nx][1] = d break else: # 이동할 수 없을 경우 방향 바꾸기 d = (d + 1) % 9 if d == 0: d = 1
구현한 코드
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
from copy import deepcopy
### 2. shark 함수
def shark(ocean, new_eat, sy, sx, sd): # 상어와 관련된 함수
global final_eat
move_fish(ocean) # 물고기 이동시키는 함수!
eat_list = []
ocean[sy][sx] = [0, 0]
nsy, nsx = sy + dirs[sd][0], sx + dirs[sd][1]
while 0 <= nsy < 4 and 0 <= nsx < 4:
if ocean[nsy][nsx][0] != 0:
# 상어가 잡아먹을 수 있는 물고기들 eat_list에 저장하기
eat_list.append([nsy, nsx, ocean[nsy][nsx][0], ocean[nsy][nsx][1]])
nsy, nsx = nsy + dirs[sd][0], nsx + dirs[sd][1]
if len(eat_list): # 먹을 물고기가 있는 경우
for eat in eat_list:
red_ocean = deepcopy(ocean)
red_ocean[eat[0]][eat[1]] = [-1, -1]
shark(red_ocean, new_eat + eat[2], eat[0], eat[1], eat[3])
else: # 먹을 물고기가 없는 경우
if new_eat > final_eat:
final_eat = new_eat
### 3. move_fish 함수
def move_fish(ocean): # 물고기 이동시키는 함수
for num in range(1, 17): # 작은 번호의 물고기 부터 이동시키기
y, x, d = -1, -1, -1
frag = False
# num의 번호를 가진 물고기 위치 찾기
for fy in range(4):
if frag: break
for fx in range(4):
if ocean[fy][fx][0] == num:
frag = True
y, x = fy, fx
d = ocean[fy][fx][1]
break
# 물고기가 있는 경우 움직이기
if [y, x, d] != [-1, -1, -1]: # 초기화 값과 다르기에 물고기 찾음!!
for _ in range(8):
ny, nx = y + dirs[d][0], x + dirs[d][1]
if 0 <= ny < 4 and 0 <= nx < 4 and ocean[ny][nx][0] != -1:
ocean[ny][nx], ocean[y][x] = ocean[y][x], ocean[ny][nx]
ocean[ny][nx][1] = d
break
else: # 이동할 수 없을 경우 방향 바꾸기
d = (d + 1) % 9
if d == 0: d = 1
### 1. 기본 설정
# ocean : 물고기 번호와 방향, 상어의 위치를 저장할 4X4 크기
ocean = [[0] * 4 for _ in range(4)]
# input 값들 알맞은 형태([물고기번호, 물고기 방향])로 ocean에 저장하기
for i in range(4):
ab_list = list(map(int, input().split()))
idx = 0
for j in range(0, 8, 2):
ocean[i][idx] = [ab_list[j], ab_list[j+1]]
idx += 1
# 상어의 위치(sh_y, sh_x)와 방향(sh_d)을 저장할 변수
sh_y, sh_x, sh_d = 0, 0, ocean[0][0][1]
# final_eat : 최종 답이 될 변수
# final_eat (0, 0)에 위치한 물고기 번호로 초기화
final_eat = ocean[0][0][0]
ocean[0][0] = [-1, -1] # 상어 위치임을 표시
dirs = [[0, 0], [-1, 0], [-1, -1], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1]]
shark(ocean, final_eat, sh_y, sh_x, sh_d)
print(final_eat)