BOJ - 청소년 상어 19236번 (python)

❓ 문제 - 백준 청소년 상어 19236번 - python 풀이법

 

출처 

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

19236번: 청소년 상어

 

 

 

📝 문제해결법

1. 이 문제는 구현+DFS로 풀었다.

• 4*4 공간의 board 안에 물고기가 들어있는 번호, 방향을 저장한다. 만약 물고기가 잡아먹혔을 때 번호를 0으로 바꾼다.
• DFS를 통해 상어가 해당 방향으로 움직였을 때, 먹은 물고기의 번호로 점수를 더해주고 상어가 먹은 물고기 번호의 합의 최대값을 갱신한다. 또한 상어가 이동한 지역의 물고기를 먹으므로 해당 지역의 물고기 번호를 0으로 변경한다.
• 상어가 물고기를 먹은 후 물고기의 움직임이 일어나는데, 물고기의 이동은 순서대로 진행되므로 보드에서 해당 물고기의 번호가 존재(먹히지 않았음)하면 해당 물고기의 방향대로 이동할 수 있다면 이동하는 곳의 위치와 현재 위치에 board 정보를 서로 변경하고, 만약 해당 방향에 이동할 수 없다면 45도 반시계 방향으로 계속 돌면서 이동할 수 있는 곳을 찾는다.
• 물고기가 다 이동한 후, 상어의 이동이 시작되는데 상어의 현재 방향대로 갈 수 있는 모든 곳에 이동이 가능하면(범위 안 넘고, 물고기가 존재함) DFS로 들어가서 물고기를 먹는다.
• 모든 DFS를 돈 후 상어가 먹은  물고기 번호의 최대값을 출력한다.

2. 문제 푼 후 느낀점

• 처음 DFS 고려 안 하고 상어가 이동할 방향에서 갈 수 있는 모든 곳의 최대값으로 이동하는 구현을 했으나 최대값, 최솟값은 완전탐색의 문제라는 의심을 항상 하고 있어야한다.
• 주어진 문제의 조건을 잘 고려해서 섬세하게 구현해야한다.

 

💻 소스코드

   
# 청소년 상어 - BOJ 19236
# DFS+구현
import copy

board = [[] for _ in range(4)]

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

for i in range(4):
    data = list(map(int, input().split()))
    fish = []
    for j in range(4):
        # 물고기 번호, 방향
        fish.append([data[2*j], data[2*j+1]-1])
    board[i] = fish


max_score = 0


def dfs(sx, sy, score, board):
    global max_score
    score += board[sx][sy][0]
    max_score = max(max_score, score)
    board[sx][sy][0] = 0

    # 물고기 움직임
    for f in range(1, 17):
        f_x, f_y = -1, -1
        for x in range(4):
            for y in range(4):
                if board[x][y][0] == f:
                    f_x, f_y = x, y
                    break
        if f_x == -1 and f_y == -1:
            continue
        f_d = board[f_x][f_y][1]

        for i in range(8):
            nd = (f_d+i) % 8
            nx = f_x + dx[nd]
            ny = f_y + dy[nd]
            if not (0 <= nx < 4 and 0 <= ny < 4) or (nx == sx and ny == sy):
                continue
            board[f_x][f_y][1] = nd
            board[f_x][f_y], board[nx][ny] = board[nx][ny], board[f_x][f_y]
            break

    # 상어 먹음
    s_d = board[sx][sy][1]
    for i in range(1, 5):
        nx = sx + dx[s_d]*i
        ny = sy + dy[s_d]*i
        if (0<= nx < 4 and 0<= ny < 4) and board[nx][ny][0] > 0:
            dfs(nx, ny, score, copy.deepcopy(board))

dfs(0, 0, 0, board)
print(max_score)