백준 19236 청소년 상어 (파이썬)

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

19236번: 청소년 상어

dfs로 모든 이동경로에 대한 최대값을 구하면 된다

 

1. 입력받은 지도에 대한 정보를 a, 물고기의 좌표를 fish에 저장한다

2. 상어의 좌표, 먹은 물고기 크기를 각각 d, cnt에 저장하고 (0, 0)에 있는 물고기에 대한 정보를 지운후 dfs를 수행한다

3. 2번 과정에서 상어가 물고기를 이미 먹었으므로 move_fish 함수를 실행해서 물고기들을 이동시킨다

4. fish 리스트의 인덱스는 (물고기의 크기 - 1) 이기 때문에 순서대로 불러와서 처리하면 작은 물고기부터 이동한다

   물고기가 이동할 수 없으면 방향을 갱신하고 continue한다

   다음칸이 빈칸이 아닌 경우에만 다음칸에 있는 물고기의 좌표를 바꿔준다

   지도에서 물고기 정보를 서로 바꿔주고 이동한 물고기의 좌표를 바꿔준다

5. 물고기 이동이 끝나면 상어가 이동한다

   만약 다음 칸이 범위를 벗어나면 최대값을 갱신한 뒤 return하고, 다음 칸이 빈칸이면 continue한다

6. 재귀를 하기 전에 a, fish, 상어가 먹게 될 물고기에 대한 정보를 temp에 저장한다

   상어의 다음 좌표, 먹은 물고기의 방향, 지금까지 먹은 물고기 크기 + 먹은 물고기의 크기 + 1를 입력해서 재귀한다

   그리고 temp값들을 불러와서 변수들을 다시 리셋한다

7. 모든 탐색을 마치고 ans를 출력한다

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, a, fish
    move_fish(x, y)
    while True:
        nx, ny = x + dx[d], y + dy[d]
        if not 0 <= nx < 4 or not 0 <= ny < 4:
            ans = max(ans, cnt)
            return
        if not a[nx][ny]:
            x, y = nx, ny
            continue

        temp_a, temp_fish = deepcopy(a), deepcopy(fish)
        temp1, temp2 = fish[a[nx][ny][0]], a[nx][ny]
        fish[a[nx][ny][0]], a[nx][ny] = [], []
        dfs(nx, ny, temp2[1], cnt + temp2[0] + 1)
        a, fish = temp_a, temp_fish
        fish[a[nx][ny][0]], a[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[a[x][y][1]], y + dy[a[x][y][1]]
                if not 0 <= nx < 4 or not 0 <= ny < 4 or (nx == sx and ny == sy):
                    a[x][y][1] = (a[x][y][1] + 1) % 8
                    continue
                if a[nx][ny]:
                    fish[a[nx][ny][0]] = [x, y]
                a[nx][ny], a[x][y] = a[x][y], a[nx][ny]
                fish[i] = [nx, ny]
                break


a = [[] 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):
        a[i].append([temp[j]-1, temp[j+1]-1])
        fish[temp[j]-1] = [i, j // 2]

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