[백준] 19236. 청소년 상어

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

19236번: 청소년 상어

구현 + 백트래킹 문제인데, '백트래킹 시 이전 상태로 되돌아가야 한다' 라는 걸 생각하지 않고 짜서 꽤나 삽질했다.

{물고기 번호:[물고기 y좌표, 물고기 x좌표]}로 구성된 딕셔너리와, maps[y좌표][x좌표] = [물고기 번호, 물고기 방향] 으로 구성된 2차원 배열을 이용하였다. 딕셔너리는 물고기 번호 순서대로 물고기가 이동하기 때문에 key를 이용해 물고기 위치를 파악하고, 방향을 바꿔가며 이동시키기 위해 사용하였다.

 

상어가 현재 상태에서 갈 수 있는 곳까지 갔다가 더이상 갈 수 없으면 다시 이전 상태를 기준으로 또 다시 갈 수 있는 곳으로 이동하기 때문에, fish_map과 fish_dict 모두를 매개 변수로 넘겨주고 이를 deepcopy를 이용해 복사한 뒤 사용해서 이전의 데이터에는 영향이 가지 않도록 해주었다. 

 

처음에는 0, 0에 있는 물고기를 일단 먹고 들어갔는데 이렇게 하니, 다음 물고기를 먹을 때 구현이 더 복잡해져서 ㅎㅁ수를 실행하잠자 deepcopy로 데이터를 복사한 후, 물고기를 먹는 것으로 해주었다.

 

물고기를 먹고나면 데이터를 -1로 초기화할 지, 그냥 빈 리스트로 둘 지 고민했는데 빈 리스트로 두는 게 if 문에서 더 간단하게 물고기 존재여부를 파악할 수 있기 때문에 빈 리스트로 갱신해주었다. 또한 물고기를 먹고 바로 ans 값을 갱신해준다. 어차피 물고기가 이동하고 나서 상어가 갈 곳이 없으면 지금 서 있는 곳의 물고기를 먹은 것까지가 현재 먹을 수 있는 최대값이기 때문에 먹자마자 바로 갱신해줘도 된다.

 

fish_move는 상어 위치, 복사된 리스트, 복사된 딕셔너리를 인자로 받아서 진행한다. fish_dict[idx] 가 존재한다면, 즉 물고기가 존재한다면 방향을 바꿔가면서 갈 수 있는 곳인지 확인하고, 갈 수 있는 곳이라면 위치를 바꿔준다. 만약 해당 위치에 물고기가 있다면 그 물고기의 위치를 바꿔주고, 없다면 idx에 해당하는 물고기의 위치와 값만 바꿔준다.

 

물고기가 이동하고 나면 상어가 자기가 가진 방향으로 갈 수 있는 칸으로 이동한다. 상어는 물고기가 있는 칸으로만 이동하며, 상어가 최대로 이동해도 maps의 최대 크기인 4까지 밖에 이동할 수 없으므로 for문은 1부터 3까지만 돌고 모두 방문하고 나면 함수가 끝나고 이전 함수로 되돌아간다.

from copy import deepcopy
import sys
input = sys.stdin.readline


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


def shark_move(shark_y, shark_x, eat_fish, fish_map, fish_dict):
    global ans
    new_maps = deepcopy(fish_map)
    new_dict = deepcopy(fish_dict)

    shark_dir = new_maps[shark_y][shark_x][1]
    shark_eat = new_maps[shark_y][shark_x][0]
    new_dict[shark_eat], new_maps[shark_y][shark_x] = [], []

    ans = max(eat_fish+shark_eat, ans)

    fish_move(shark_y, shark_x, new_maps, new_dict)
    temp_y, temp_x = shark_y, shark_x
    for k in range(1, 4):
        ny, nx = temp_y + dy[shark_dir], temp_x+dx[shark_dir]
        if 0 <= nx < 4 and 0 <= ny < 4 and new_maps[ny][nx]:
            shark_move(ny, nx, eat_fish + shark_eat, new_maps, new_dict)
        temp_y, temp_x = ny, nx


def fish_move(sy, sx, fish_map, fish_dict):
    for idx in range(1, 17):
        if fish_dict[idx]:
            y, x = fish_dict[idx][0], fish_dict[idx][1]
            fish_d = fish_map[y][x][1]
            for k in range(8):
                new_d = (fish_d + k) % 8
                ny = y + dy[new_d]
                nx = x + dx[new_d]
                if 0 <= ny < 4 and 0 <= nx < 4 and (ny, nx) != (sy, sx):
                    fish_map[y][x][1] = new_d
                    if fish_map[ny][nx]:
                        fish_dict[fish_map[ny][nx][0]] = [y, x]
                    fish_dict[idx] = [ny, nx]
                    fish_map[ny][nx], fish_map[y][x] = fish_map[y][x], fish_map[ny][nx]
                    break


input_data = [list(map(int, input().split())) for _ in range(4)]
maps = [[], [], [], []]
fish = {}
ans = 0

for i in range(4):
    for j in range(0, 8, 2):
        maps[i].append([input_data[i][j], input_data[i][j+1]-1])
        fish[input_data[i][j]] = [i, j//2]


shark_move(0, 0, 0, maps, fish)
print(ans)