19236_청소년 상어 (Python)
0. 출처
1. 기록
2. 풀이
(1) 아이디어, 시간복잡도, 자료구조
1. 아이디어
>> [[[물고기번호, 방향], [물고기번호, 방향], [물고기번호, 방향]],
[[물고기번호, 방향], [물고기번호, 방향], [물고기번호, 방향]],]
>> 이렇게 3차원 배열형태로 담는다.
----------------------------------------------------------------------------------------------
>> 상어는 [0] 을 먹으면 [0][0] 의 물고기번호를 누적하고 [0][1] 의 방향을 갖게된다.
>> 이후 물고기번호 1번부터 끝번호까지 해당 방향으로 이동할 수 있으면 이동하고
>> 이동할 수 없으면 45도 반시계방향으로 회전한다. (해당 방향에 상어가 있는 경우도 이동할 수 없는 경우이다.)
>> 상어는 [0][1] 방향을 가졌으므로
>> 해당 방향으로 1번 이동하는 경우, 2번 이동하는 경우, ...를 모든 경우르 비교한다.
>> 상어는 여러칸을 이동할 수 있기 때문에 백트래킹으로 풀어야한다. ★★★★★
----------------------------------------------------------------------------------------------
>> 위의 경우를 계속 반복하고 상어가 더 이상 이동할 수 없는 경우 누적된 물고기 번호 합을 리턴한다.
2. 시간복잡도
>>
3. 자료구조
>>
(2) 예제 입력, 예제 출력
- 예제 입력 1 -
7 6 2 3 15 6 9 8
3 1 1 8 14 7 10 1
6 1 13 6 4 3 11 4
16 1 8 7 5 2 12 2
- 예제 출력 1 -
33
- 예제 입력 2 -
16 7 1 4 4 3 12 8
14 7 7 6 3 4 10 2
5 2 15 2 8 3 6 4
11 8 2 4 13 5 9 4
- 예제 출력 2 -
43
- 예제 입력 3 -
12 6 14 5 4 5 6 7
15 1 11 7 3 7 7 5
10 3 8 3 16 6 1 1
5 8 2 7 13 6 9 2
- 예제 출력 3 -
76
- 예제 입력 4 -
2 6 10 8 6 7 9 4
1 7 16 6 4 2 5 8
3 7 8 6 7 6 14 8
12 7 15 4 11 3 13 3
- 예제 출력 4 -
39
(3) 코드
import copy
n = int(4)
m = int(8)
temp_graph = [list(map(int, input().split())) for _ in range(4)]
graph = list([] * n for _ in range(n))
for i in range(n):
for j in range(0, m, 2):
graph[i].append(temp_graph[i][j:j + 2])
for i in range(n):
for j in range(n):
graph[i][j][1] -= 1
# 방향
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]
# 상어가 [0][0]의 위치로 간다.
# [행][열][0] : 먹이번호
# [행][열][1] : 방향
max_score = 0
def dfs(sx, sy, total, graph):
global max_score
total += graph[sx][sy][0]
max_score = max(max_score, total)
graph[sx][sy][0] = 0
# 물고기 움직임
for num in range(1, 17):
f_x, f_y = -1, -1
for x in range(n):
for y in range(n):
if graph[x][y][0] == num:
f_x, f_y = x, y
break
if f_x == -1 and f_y == -1:
continue
f_d = graph[f_x][f_y][1]
for i in range(8):
nd = (f_d + i) % 8
nx = f_x + dx[nd]
ny = f_y + dy[nd]
# 범위를 벗어나는 경우 or 상어가 있는 경우는 건너 뛴다.
if not (0 <= nx < 4 and 0 <= ny < 4) or (nx == sx and ny == sy):
continue
# 조건을 만족하는 경우 해당 물고기의 방향
graph[f_x][f_y][1] = nd
# 해당 물고기와 해당 물고기가 가리키는 방향에 위치한 물고기의 위치를 바꿔준다.
graph[f_x][f_y], graph[nx][ny] = graph[nx][ny], graph[f_x][f_y]
break
s_dir = graph[sx][sy][1]
for i in range(1, 4):
nx = sx + dx[s_dir] * i
ny = sy + dy[s_dir] * i
if (0 <= nx < 4 and 0 <= ny < 4) and graph[nx][ny][0] > 0:
dfs(nx, ny, total, copy.deepcopy(graph))
dfs(0, 0, 0, graph)
print(max_score)
(4) 정리
(5) 참고
참고 풀이