[BAEKJOON python] 19236_청소년 상어

청소년 상어
4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다
공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호
한 칸에는 물고기가 한 마리 존재
    물고기는 번호와 방향을 가지고 있다
    번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수
    두 물고기가 같은 번호를 갖는 경우는 없다
    방향은 8가지 방향(상하좌우, 대각선) 중 하나

청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다
청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다
상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다
이후 물고기가 이동한다

1) 물고기는 번호가 작은 물고기부터 순서대로 이동한다
물고기는 한 칸을 이동
    이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸
    이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸
각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전
이동할 수 있는 칸이 없으면 이동을 하지 않는다
물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동

2) 물고기의 이동이 모두 끝나면 상어가 이동한다
상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다
상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다
이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다.
물고기가 없는 칸으로는 이동할 수 없다
상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다
상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복

상어가 먹을 수 있는 물고기 번호의 합의 최댓값

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보
    물고기의 정보는 두 정수 ai, bi
    ai는 물고기의 번호, bi는 방향 (1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗)

import copy

board = [[] for _ in range(4)]

# 물고기 방향 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

for i in range(4):
    data = list(map(int, input().split()))
    fish = []
    # 물고기 번호, 방향
    for j in range(4):
        fish.append([data[2 * j],
                     data[2 * j + 1] - 1])  # 방향에서 -1 이유는 : 인덱스는 0부터 시작이라 ㅎ
    # 물고기가 들어있는 번호, 방향을 저장
    board[i] = fish

# 상어가 먹을 수 있는 물고기 번호의 합의 최댓값
max_score = 0


def dfs(sx, sy, score, board):
    global max_score
    # 먹은 물고기의 번호로 점수를 더해주고
    score += board[sx][sy][0]
    # 상어가 먹은 물고기 번호의 합의 최대값을 갱신
    max_score = max(score, max_score)
    board[sx][sy][0] = 0

    # 1) 물고기 움직임
    for f in range(1, 17):
        f_x, f_y = -1, -1
        for x in range(4):
            for y in range(4):
                # 1부터 16까지 차례대로 물고기 이동
                if board[x][y][0] == f:
                    f_x, f_y = x, y
                    break
        if f_x == -1 and f_y == -1:
            continue

        # 물고기 방향
        f_d = board[f_x][f_y][1]
        for i in range(8):
            # 반시계로 45도씩
            nd = (f_d + i) % 8
            nx = f_x + dx[nd]
            ny = f_y + dy[nd]
            # 격자판을 안 넘어갔고, 상어와 같은 위치라면 계속 돌려~
            if not (0 <= nx < 4 and 0 <= ny < 4) or (nx == sx and ny == sy):
                continue
            # 방향 갱신
            board[f_x][f_y][1] = nd
            # 이동한 애랑, 이동할 애랑 위치 바꾸기
            board[f_x][f_y], board[nx][ny] = board[nx][ny], board[f_x][f_y]
            break

    # 2) 상어 이동 -> 먹음
    s_d = board[sx][sy][1]  # 상어가 위치한 곳 = 물고기 위치 (방향)
    for i in range(1, 5):
        nx = sx + dx[s_d] * i
        ny = sy + dy[s_d] * i
        if (0 <= nx < 4 and 0 <= ny < 4) and board[nx][ny][0] > 0:
            # 상어 이동할 때마다 최대값 갱신
            dfs(nx, ny, score, copy.deepcopy(board))


dfs(0, 0, 0, board)
print(max_score)

---

예제 입력

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

예제 출력

76

 

 

 

재밌는데?

왜 혼자 못할까 ㅋㅋㅋ

아직. 분석 방법이 어려움 ㅠ

https://developer-ellen.tistory.com/68

감사합니당ㅎㅎ