boj 19236 청소년 상어 (골드2)

문제

https://www.acmicpc.net/problem/19236

삼성 기출

풀이

from copy import deepcopy

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

answer = 0
sea = [[0] * 4 for _ in range(4)]

for j in range(4):
    arr = list(map(int,input().split()))
    for i in range(4):
        sea[j][i] = (arr[2*i], arr[2*i+1])

def move_fish(back,k,shark):
    for i in range(4):
        for j in range(4):
            if back[i][j] == -1: continue # 빈칸이면 패스
            if back[i][j][0] == k:
                dir = back[i][j][1]
                for _ in range(8):  # 최대 8방향 탐
                    ny = i + dy[dir]
                    nx = j + dx[dir]

                    if 0 <= ny < 4 and 0 <= nx < 4 and (ny, nx) != shark:
                        back[i][j] = (back[i][j][0],dir)
                        back[ny][nx], back[i][j] = back[i][j], back[ny][nx]
                        return

                    else:
                        dir = (dir+1) % 9
                        if dir == 0:
                            dir += 1


def play(shark,sea,answer):
    back =deepcopy(sea)
    answer += back[shark[0]][shark[1]][0] #상어가 먹은 물고기 더해줌
    back[shark[0]][shark[1]] = (0,back[shark[0]][shark[1]][1])  #상어가 있는곳 물고기넘버 0으로 벼경
    for k in range(1,17):  # 물고기 이동
        move_fish(back,k,shark)
    shark_dir = back[shark[0]][shark[1]][1]
    for i in range(1,4):
        ny = shark[0] + dy[shark_dir] * i
        nx = shark[1] + dx[shark_dir] * i
        if 0 <= ny < 4 and 0 <= nx < 4 and back[ny][nx] != -1: #맵 안에 있고 빈칸이 아니면 먹을수 있음.
            back2 = deepcopy(back)
            back2[shark[0]][shark[1]] = -1
            play((ny,nx),deepcopy(back2),answer)
    answer_list.append(answer)
    return

play((0,0),sea,answer)
print(max(answer_list))

결과