[백준, 삼성 기출] 19236_청소년 상어 (Python)

19236_청소년 상어 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 2)
• 링크 : 19236번: 청소년 상어

1. 기록

• 22/04/21 (목)

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) 참고

참고 풀이