Q47. 청소년상어

19236번: 청소년 상어 (acmicpc.net)

19236번: 청소년 상어

 

진짜 어렵네 ㅋㅋㅋㅋㅋㅋㅋㅋ

가독성을 위해 함수로 많이 나눠놨다

솔직히 이거 답지 아니었음 못풀었음

내 수준이 어느정도인지 깨닫게 해주는 문제

자괴감 + 1

삼전 문제 쉽다고 들었는데 내 기준으로 전혀 아닌듯;;

 

import copy

dx = [-1,-1,0,1,1,1,0,-1]
dy = [0,-1,-1,-1,0,1,1,1]

grid = []
for i in range(4):
    line = list(map(int, input().split()))
    grid.append([])
    for j in range(4):
        grid[i].append([line[j * 2], line[j * 2 + 1] - 1])

def eat_fish(grid, curx, cury):
    fishnum = grid[curx][cury][0]
    grid[curx][cury][0] = -1
    return fishnum

def find_next_pos(grid, curx, cury):
    direction = grid[curx][cury][1]

    nx = curx
    ny = cury

    nxt_pos = []

    for i in range(3):
        nx += dx[direction]
        ny += dy[direction]
    
        if nx >= 0 and nx < 4 and ny >= 0 and ny < 4 and grid[nx][ny][0] != -1:
            nxt_pos.append((nx, ny))
    
    return nxt_pos

def find_fish(grid, fish_num):
    for i in range(4):
        for j in range(4):
            if grid[i][j][0] == fish_num:
                return (i, j)
    return None

def print_grid(grid):
    for line in grid:
        print(line)
    print()

def move(grid, curx, cury):
    for fish_num in range(1,17):
        fish_pos = find_fish(grid, fish_num)

        if fish_pos:
            x = fish_pos[0]
            y = fish_pos[1]
            direction = grid[x][y][1]

            for i in range(8):
                nx = x + dx[direction]
                ny = y + dy[direction]

                if nx >= 0 and nx < 4 and ny >= 0 and ny < 4 and not (nx == curx and ny == cury):
                    grid[x][y][1] = direction
                    grid[x][y], grid[nx][ny] = grid[nx][ny], grid[x][y]
                    break

                direction = (direction + 1) % 8

totalmax = 0
def dfs(grid, curx, cury, total):
    global totalmax

    # grid 복사
    grid = copy.deepcopy(grid)

    # 상어가 현재 위치의 물고기를 먹고 물고기번호 더해주기
    total += eat_fish(grid, curx, cury)

    # 물고기들 이동!
    move(grid, curx, cury)

    # 상어가 갈수있는 다음포지션 리스트
    nxt_list = find_next_pos(grid, curx, cury)

    # 갈 수 있는 곳이 없으면 최대값 갱신하고 리턴
    if not nxt_list:
        totalmax = max(totalmax, total)
        return
    
    # 갈 수 있는 곳 있으면 dfs 수행
    for x, y in nxt_list:
        dfs(grid, x, y, total)

dfs(grid, 0, 0, 0)
print(totalmax)