306. 청소년 상어

백준

1. 백트레킹

정해

import sys
from copy import deepcopy

input = sys.stdin.readline
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

def dfs(x, y, d, cnt):
    global ans, board, fish
    move_fish(x, y)
    #상어 이동
    while True:
        nx, ny = x + dx[d], y + dy[d]
        #다음 칸이 범위를 벗어나면 최대값을 갱신한 뒤 return
        if not 0 <= nx < 4 or not 0 <= ny < 4:
            ans = max(ans, cnt)
            return
        #다음 칸이 빈칸이면 continue한다
        if not board[nx][ny]:
            x, y = nx, ny
            continue
        
        #재귀를 하기 전에 board, fish, 상어가 먹게 될 물고기에 대한 정보를 temp에 저장한다
        temp_board, temp_fish = deepcopy(board), deepcopy(fish)
        temp1, temp2 = fish[board[nx][ny][0]], board[nx][ny]
        fish[board[nx][ny][0]], board[nx][ny] = [], []
        #상어의 다음 좌표, 먹은 물고기의 방향, 지금까지 먹은 물고기 크기 + 먹은 물고기의 크기 + 1를 입력해서 재귀한다
        dfs(nx, ny, temp2[1], cnt + temp2[0] + 1)
        board, fish = temp_board, temp_fish
        #변수들을 다시 리셋한다
        fish[board[nx][ny][0]], board[nx][ny] = temp1, temp2
        x, y = nx, ny


def move_fish(sx, sy):
    for i in range(16):
        if fish[i]:
            x, y = fish[i][0], fish[i][1]
            for _ in range(9):
                nx, ny = x + dx[board[x][y][1]], y + dy[board[x][y][1]]
                if not 0 <= nx < 4 or not 0 <= ny < 4 or (nx == sx and ny == sy):
                    #물고기가 이동할 수 없으면 방향을 갱신
                    board[x][y][1] = (board[x][y][1] + 1) % 8
                    continue
                #빈칸이 아닌 경우에 물고기의 좌표 변경
                if board[nx][ny]:
                    fish[board[nx][ny][0]] = [x, y]
                #이동한 물고기의 좌표를 바꿔준다
                board[nx][ny], board[x][y] = board[x][y], board[nx][ny]
                fish[i] = [nx, ny]
                break


board = [[] for _ in range(4)]
fish = [[] for _ in range(16)]
for i in range(4):
    temp = list(map(int, input().split()))
    for j in range(0, 7, 2):
        board[i].append([temp[j]-1, temp[j+1]-1])
        fish[temp[j]-1] = [i, j // 2]

ans = 0
d, cnt = board[0][0][1], board[0][0][0] + 1
fish[board[0][0][0]], board[0][0] = [], []
dfs(0, 0, d, cnt)
print(ans)

상어에서 막힘

from collections import defaultdict
import math
board = [[0] * 4 for _ in range(4)]
#1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]
fish = defaultdict(list)
for i in range(4):
    #물고기 번호, 방향
    row = list(map(int, input().split()))
    for j in range(0, 7, 2):
        #x, y
        fish[row[j]] = [i, j // 2, row[j + 1] - 1]
        #물고기 번호, 방향
        board[i][j // 2] = [row[j], row[j + 1] - 1]




while True:
    #물고기 이동
    for i in range(1, 17):
        if i in ate: #먹었으면 이동 x
            continue 
        x, y, d = fish[i]
        # 빈 칸과 다른 물고기가 있는 칸, 
        # 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸
        for _ in range(8):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < 4 and 0 <= ny < 4 and board[nx][ny] != 2 :
                if board[nx][ny] == 0: #빈 칸
                    board[x][y] = 0
                    board[nx][ny] = board[x][y]
                    break
                else: # 다른 물고기가 있는 칸
                    num, dir = board[nx][ny]
                    board[x][y], board[nx][ny] = board[nx][ny], board[x][y]
                    fish[i] = [nx, ny, d]
                    fish[num] = [x, y, dir]
                    break          
            else:
                d = d + 1 % 8

    #상어 이동
    #물고기 번호 합 가장 큰거??
    can = []
    nsx, nsy = sx, sy
    while nsx < 4 and nsy < 4:
        nsx = nsx + dx[sd]
        nsy = nsy + dy[sd]
        if 0 <= nsx < 4 and 0 <= nsy < 4 and board[nx][ny] != 0:
            can.append([nsx, nsy])

    print(can)

        

            
            

    



#