19236: 청소년 상어

풀이 시간

• 2h 30m
• dfs + 백트래킹 관련 문제를 더 많이 풀어봐야겠다

구현 방식

• "상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다."
  --> 이 부분에서 dfs로 구현해야한다는 사실을 알 수 있다
  --> 처음에는 메인 자료를 board(2차원 list)랑 fish(dictionary)로 나누어서 board에는 물고기의 번호를, fish에는 물고기의 번호를 key로, 좌표와 방향을 value로 하여 저장하려 했으나, dfs 구현 과정에 있어서 그냥 board(2차원 list)에 물고기의 번호와 방향을 모두 저장하는 식으로 처리하는게 더 편리했다

dfs(sx, sy, local_total_ate, board) 구현 흐름

• 상어가 (sx, sy)에 있는 물고기를 먹음
  -> local_total_ate에 board[sx][sy][0]를 더해주고 total_ate를 최댓값으로 갱신
  -> board[sx][sy][0]을 0으로 갱신 + sd(상어의 방향)을 board[sx][sy][1]로 갱신

• 물고기 이동
  -> 1부터 16까지 for문을 돌면서 차례대로 물고기의 이동을 수행해준다
  -> (nfx, nfy)가 범위를 넘거나 (sx, sy)와 같은 경우를 제외해줘야한다

• 상어 이동
  -> 이 부분에서 재귀 호출을 해줘야한다
  -> "물고기가 없는 칸으로는 이동할 수 없다."라는 조건에따라 x가 board[x][y][0]이 0인 경우를 제외해줘야한다
  -> 여기서 주의해줘야할 부분은 board를 인자로 넘겨줄 때, deepcopy를 통해 call by value로 dfs를 호출해줘야한다는 점이다

코드

import sys
import copy

dx = (-1, -1, 0, 1, 1, 1, 0, -1)
dy = (0, -1, -1, -1, 0, 1, 1, 1)

def dfs(sx, sy, local_total_ate, board):
    global total_ate

    ##### 상어가 (sx, sy)에 있는 물고기를 먹음
    local_total_ate += board[sx][sy][0]
    total_ate = max(local_total_ate, total_ate)
    board[sx][sy][0] = 0
    sd = board[sx][sy][1]

    ##### 물고기 이동
    for fish in range(1, 17):
        fx = -1; fy = -1
        for i in range(4):
            for j in range(4):
                if board[i][j][0] == fish:
                    fx = i; fy = j; break
        if fx == -1 and fy == -1: continue
        fd = board[fx][fy][1]
        for i in range(8):
            nfd = (fd + i) % 8
            nfx = fx + dx[nfd]; nfy = fy + dy[nfd]
            if 0 <= nfx < 4 and 0 <= nfy < 4 and (nfx != sx or nfy != sy):
                board[fx][fy][1] = nfd
                board[fx][fy], board[nfx][nfy] = board[nfx][nfy], board[fx][fy]
                break

    ##### 상어 이동
    x = sx; y = sy
    for i in range(3):
        x += dx[sd]; y += dy[sd]
        if 0 <= x < 4 and 0 <= y < 4 and board[x][y][0] != 0:
            dfs(x, y, local_total_ate, copy.deepcopy(board))


board = [[0] * 4 for _ in range(4)]
for n in range(4):
    a1, b1, a2, b2, a3, b3, a4, b4 = map(int, sys.stdin.readline()[:-1].split()); b1 -= 1; b2 -= 1; b3 -= 1; b4 -= 1
    board[n][0] = [a1, b1]; board[n][1] = [a2, b2]; board[n][2] = [a3, b3]; board[n][3] = [a4, b4]

total_ate = 0
dfs(0, 0, 0, board)
print(total_ate)

결과