✅문제 요약

1. 4x4 격자, 한 칸 당 물고기는 한마리만 존재(번호와 방향을 가지고 있음
   1) 물고기 번호는 16이하 자연수, 같은 번호 물고기는 없음
   2) 방향은 대각선 포함 8방향
2. 0,0 위치에 청소년 상어가 들어가고, 해당 물고기를 먹고 방향을 가짐
3. 이후 물고기가 이동
   1) 번호가 작은 물고기 부터 한 칸 이동(상어가 있거나 경계선은 넘을 수 없음
   2) 이동할 수 있는 방향이 있을 때 까지 반시계방향으로 45도 회전
   3) 다른 물고기가 있는 위치로 이동할 때는 서로 위치를 바꿈
   4) 이동할 수 있는 방향이 없다면 이동하지 않는다
4. 물고기 이동 후 다시 상어 이동
   1) 한 번에 여러 칸 이동 가능
   2) 해당 칸에 물고기가 있다면 먹고, 방향을 가짐
   3) 지나가는 칸에 있는 물고기는 먹지 않는다.
   4) 물고기가 없는 칸으로 이동할 수 없다.
   5) 이동할 수 없다면 종료
5. 3번 부터 반복

✅문제 풀이

삼성은 보통 구현, 시뮬레이션을 통한 그래프탐색, DP 위주의 문제를 많이 내는데, 그 중에서도 은근 까다로운 문제였다고 생각한다.

문제의 핵심은 2차원 배열 참조

먼저 4x4 배열이기에 덜 까다롭지만 이 문제의 핵심은 리스트 참조를 파악하냐 안하냐의 차이가 크다.

먼저 상어가 0,0 에 들어가서 해당 물고기의 방향 갖고, 그 물고기의 크기를 결괏값에 포함시킨다.

그 다음 물고기가 이동하고, 이미 물고기가 있는 자리는 스왑한다.
이동이 끝나고 상어가 격자 끝까지 탐색을 하며 물고기가 있는 자리로 이동하는데, 이 2가지 포인트에서 2차원 리스트 참조가 중요하다.

상어가 이동을 했을때 그 위치 물고기는 사라지고, 상어위치로 바뀐다.
만약 같은 방향에 물고기가 또 있을 때는 사라진 물고기를 다시 복원 시키고, 다른 물고기 자리로 상어가 이동해야한다.

상어가 이동할 때마다 물고기가 이동하는 배열에 영향을 주기에 깊은 복사를 사용하여 재귀를 해줘야 한다.

그렇지 않으면 상어가 이동한 방향의 이전 위치 물고기가 사라진 상태 배열에서 물고기가 이동하기 때문에 물고기가 이동할 때 에러가 많이 난다

mat = [[[], [], [], []] for _ in range(4)]
info = [0 for _ in range(17)]
dp = [(-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)]

# 물고기 번호와 방향을 담음
for i in range(4):
    line = list(map(int, input().split()))
    for j in range(0, 8, 2):

        # 격자에 물고기 번호와 방향을 저장
        mat[i][j//2] = [line[j], line[j+1]-1]
        # 물고기 번호 별 행열번호 저장
        info[line[j]] = (i, j//2)


# 상어 초기 시작
first = mat[0][0]

# 위치, 방향
shark = (0, 0, first[1])

# 먹은 양
answer = first[0]

# 0, 0 위치 초기화
info[first[0]] = 0
mat[0][0] = -1


def move(arr, fishes, now, cnt):
    # 물고기 이동
    for num in range(1, 17):
        # 먹힌 물고기는 pass
        if fishes[num] == 0:continue

        # 물고기 행, 열
        r, c = fishes[num]
        # 번호, 방향
        _, p = arr[r][c]

        # 8방향 탐색
        for d in range(8):
            # 다음 이동 방향
            head = (p+d)%8
            nr, nc = r + dp[head][0], c + dp[head][1]

            # 이동할 수 있다면
            if 0 <= nr < 4 and 0 <= nc < 4 and arr[nr][nc] != -1:
                # 해당 위치에 물고기가 있다면
                if arr[nr][nc]:
                    # 해당 위치 물고기 번호
                    tmp_num, tmp_head = arr[nr][nc]
                    # 서로 위치 교환
                    arr[r][c], arr[nr][nc] = arr[nr][nc], (num, head)
                    # 현재 와 해당 위치 물고기의 위치 정보 수정
                    fishes[num], fishes[tmp_num] = (nr, nc), (r, c)

                # 빈 자리라면
                else:
                    arr[r][c], arr[nr][nc] = 0, (num, head)
                    fishes[num] = (nr, nc)

                break
                # 위치 교환 했다면 브레이크
                # 위치 교환 못했다면 for문을 돌며 방향 탐색. 모든 방향 이동 불가면 제자리

    global answer

    # 상어 위치와 방향
    x, y, s = now

    n = 1
    while True:
    	# 상어의 이동 위치
        nx, ny = x+dp[s][0]*n, y+dp[s][1]*n
        if 0 <= nx < 4 and 0 <= ny < 4:
        	# 물고기가 있는 곳이라면
            if arr[nx][ny]:

                size, next_s = arr[nx][ny]
                arr[x][y], arr[nx][ny] = 0, -1
                fishes[size] = 0
                
                # 깊은 복사 재귀
                move([l[:] for l in arr], fishes[:], (nx, ny, next_s), cnt+size)
                
                # 물고기 위치 복원
                fishes[size] = (nx, ny)
                arr[x][y], arr[nx][ny] = -1, (size, next_s)
                
        # 격자 밖으로 나갔다면 반복 종료
        else:
            answer = max(answer, cnt)
            break
        n += 1


move(mat, info, shark, answer)


print(answer)