[BAEKJOON] 19236번: 청소년 상어

 

https://www.acmicpc.net/problem/19236 - 19236. 청소년 상어

역시 다른 사람이 쓴 코드를 분석해가면서 알고리즘을 익히는 중.

---

import copy

def moveFish(fishes, board, shark):     # 물고기들의 움직임
    for fishNum in sorted(fishes.keys()):
        x, y, d = fishes[fishNum]
        for i in range(8):
            nx = x + dx[(d+i)%8]
            ny = y + dy[(d+i)%8]

            # 가고자 하는 곳이
            if nx < 0 or ny < 0 or nx >= 4 or ny >= 4:      # 범위 벗어남 => 이동 불가
                continue
            if shark[0] == nx and shark[1] == ny:       # 상어가 있는 위치
                continue
            if board[nx][ny] != -1:     # 물고기가 있을 때
                fishes[board[nx][ny]][0] = x
                fishes[board[nx][ny]][1] = y
            
            fishes[fishNum] = [nx, ny, (d+i)%8]     # 바뀐 위치 업데이트
            board[nx][ny], board[x][y] = board[x][y], board[nx][ny]
            break


def dfs(score, shark, newFishes, newBoard):
    global answer
    moveFish(newFishes, newBoard, shark)
    t = 1
    
    while True:     # 상어 움직임 구하기
        nx = shark[0] + dx[shark[2]]*t
        ny = shark[1] + dy[shark[2]]*t

        if nx < 0 or ny < 0 or nx >= 4 or ny >= 4:
            answer = max(answer, score)
            return
        if newBoard[nx][ny] == -1:      # 이동한 곳에 물고기가 없으면
            t += 1                      # 한 칸 더 움직인다
            continue

        board = copy.deepcopy(newBoard)
        fishes = copy.deepcopy(newFishes)
        tmpNum = board[nx][ny]      # 이동할 좌표에 있는 물고기 번호
        tmpFish = fishes[tmpNum]    # 먹힐 물고기의 x,y,d
        board[nx][ny] = -1
        del fishes[tmpNum]
        dfs(score+tmpNum, [nx, ny, tmpFish[2]], fishes, board)
        t += 1


fishes = dict()     # 물고기 번호: [x좌표, y좌표, 방향]
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

board = [[0] * 4 for _ in range(4)]     # 물고기가 위치한 격자

for i in range(4):
    arr = list(map(int, input().split()))
    for j in range(0, 8, 2):
        a, b = arr[j], arr[j+1]     # a: 물고기 번호, b: 물고기 방향
        board[i][j//2] = a
        fishes[a] = [i, j//2, b-1]

shark = [0, 0, 0]       # 상어의 초기 상태
score = board[0][0]     # 상어가 (0,0)에 있던 물고기 먹음
shark[2] = fishes[score][2]     # 상어의 방향 = 먹은 물고기의 방향
del fishes[score]
board[0][0] = -1
answer = 0

dfs(score, shark, fishes, board)

print(answer)