boj 23290 마법사 상어와 복제 (골드1)

문제

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

내풀이

from collections import defaultdict
m, s = map(int,input().split())

fish = [list(map(int, input().split())) for _ in range(m)]  ## y, x, dir
shark = list(map(int,input().split()))  ## y,x
shark = [shark[0]-1,shark[1]-1]
fish = [[[fish[i][0]-1,fish[i][1]-1], fish[i][2]-1] for i in range(len(fish))]
## [[y,x], dir]

d = defaultdict(list)  # 물고기들 위치 종합저장


def make_dict():
    global d
    d = defaultdict(list)
    for i in range(len(fish)):
        (y,x),dir = fish[i]
        d[(y,x)].append(dir)

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

## 물고기 이동방향
dy = [0,-1,-1,-1,0,1,1,1]
dx = [-1,-1,0,1,1,1,0,-1]

## 상어 이동방향
dy2 = [-1,0,1,0]
dx2 = [0,-1,0,1]


def can_move(y,x):
    if [y,x] != shark and 0 <=y<4 and 0<=x<4 and smell[y][x] == 0:
        return True

    else:
        return False

def move_fish():   ##2

    global fish
    temp = []
    for i in range(len(fish)):
        move = False  ## 물고기 움직였는지 여부
        cur_y, cur_x, dir = fish[i][0][0],fish[i][0][1], fish[i][1]

        for _ in range(8):
            ny, nx = cur_y + dy[dir%8], cur_x + dx[dir%8]
            if can_move(ny,nx):
                move = True
                temp.append([[ny,nx],dir%8]) # 물고기 이동
                break

            else:
                dir -= 1  ## 반시계 회전

        if not move:
            temp.append([[cur_y,cur_x],dir%8])

    fish = [temp[i][:] for i in range(len(temp))]
    make_dict()


roots = []
max_kill = -1

def find_shark_roots(lst,num, cord, visited):  ##[('111',4)] 이런식
    global max_kill
    global roots
    if len(lst) == 3:
        if num > max_kill:
            roots = [(lst,num,cord,visited)]
            max_kill = num
        # roots.append((lst,num, cord,visited))
        return

    else :
        y,x = cord
        for i in range(4):
            ny, nx = y + dy2[i], x + dx2[i]
            if ny < 0 or ny >= 4 or nx < 0 or nx >= 4: continue
            if (ny,nx) in d and (ny,nx) not in visited:
                eat_count = len(d[(ny,nx)])
                find_shark_roots(lst + str(i),num+ eat_count,[ny,nx], visited + [(ny,nx)])
            else :
                find_shark_roots(lst + str(i),num,[ny,nx], visited + [(ny,nx)])

def move_shark():
    global roots
    global fish
    global shark
    global max_kill
    roots = []
    max_kill = -1

    find_shark_roots('',0,shark,[])
    # roots.sort(key = lambda x:(-x[1],x[0][0],x[0][1],x[0][2]))
    print(roots)
    y,x = shark
    for (a,b) in roots[0][3]:
        if (a,b) in d:
            del d[(a,b)]
            smell[a][b] = 3
        y,x = a,b

    shark = [y,x]

    temp = []
    for k, v in d.items():
        (ny,nx), dir_list = k, v
        for dir in dir_list:
            temp.append([[ny,nx],dir])

    fish = [temp[i][:] for i in range(len(temp))]

def remove_smell():
    for i in range(4):
        for j in range(4):
            smell[i][j] -= 1 if smell[i][j] >= 1 else 0

for t in range(s):
    make_dict()
    copied_fish = [fish[i][:] for i in range(len(fish))] ## 1. 물고기 복사본 저장
    move_fish() ## 2. 모든 물고기 이동
    move_shark() ## 3. 상어이동
    remove_smell()  ##  4. 냄새 사라짐
    fish += copied_fish

print(len(fish))