135. [삼성기출31]Python 백준 19236 번 청소년 상어

안녕하세요 코딩하는 덕구입니다.

백준 19236 청소년 상어입니다.

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

19236번: 청소년 상어

백준 19236 청소년 상어 정답코드 입니다. 설명은 아래에 있습니다.

from copy import deepcopy
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]
fishes = [[] for _ in range(0, 17)]
board = [[] for _ in range(4)]
for i in range(4):
    tmp = list(map(int, input().split()))
    cnt = 0
    for j in range(4):
        board[i].append([tmp[cnt], tmp[cnt + 1] - 1])
        fishes[tmp[cnt]] = [i, j]
        cnt += 2

def debug(board):
    for i in range(4):
        for j in range(4):
            print(board[i][j], end = " ")
        print("")
    print("")

def move_shark(board, fishes, res, x, y, depth):
    num = board[x][y][0]
    res += num
    d = board[x][y][1]
    board[x][y] = -1
    fishes[num] = 0
    global ans
    ans = max(ans, res)
    move_fish(board, fishes)
    board[x][y] = 0

    for _ in range(4):
        x, y = dx[d] + x, dy[d] + y
        if 0 <= x < 4 and 0 <= y < 4:
            if board[x][y] != 0:
                move_shark(deepcopy(board), deepcopy(fishes), res, x, y, depth + 1)

def move_fish(board, fishes):
    for i in range(1, 17):
        if fishes[i] == 0:
            continue
        else:
            x, y = fishes[i]
            d = board[x][y][1]
            for j in range(1, 9):
                nx, ny = dx[d] + x, dy[d] + y
                if 0 <= nx < 4 and 0 <= ny < 4:
                    if board[nx][ny] == 0:
                        board[x][y][1] = d
                        tmp = board[nx][ny]
                        board[nx][ny] = board[x][y]
                        board[x][y] = tmp
                        fishes[i] = [nx, ny]
                        break

                    elif board[nx][ny] != -1:
                        board[x][y][1] = d
                        new_fish = board[nx][ny][0]
                        tmp = fishes[i]
                        fishes[i] = fishes[new_fish]
                        fishes[new_fish] = tmp

                        tmp = board[nx][ny]
                        board[nx][ny] = board[x][y]
                        board[x][y] = tmp
                        break
                d = (d + 1) % 8

ans = 0
move_shark(board, fishes, 0, 0, 0, 0)
print(ans)

 

문제 접근

1. 상어의 움직임과 물고기의 움직임을 구현합니다.

2. 상어의 움직임은 dfs로 구현하여 상어의 이동마다 달라지는 결과를 모두 탐색합니다.

3. 최대값을 업데이트 합니다.

 

Python 코드 구현

먼저 물고기를 board위에 표현합니다.

또한 1번부터 16번 까지의 물고기의 좌표를 저장할 fishes를 구현합니다.

from copy import deepcopy
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]
fishes = [[] for _ in range(0, 17)]
board = [[] for _ in range(4)]
for i in range(4):
    tmp = list(map(int, input().split()))
    cnt = 0
    for j in range(4):
        board[i].append([tmp[cnt], tmp[cnt + 1] - 1])
        fishes[tmp[cnt]] = [i, j]
        cnt += 2

 

상어의 움직임을 표현할 함수를 구현합니다. depth는 디버깅할 때 사용하였는데 없어도 상관 없습니다.

정해진 좌표에 상어를 이동시킨 후 물고기를 잡아먹습니다.  

점수를 증가시킨 후, 해당 물고기의 좌표를 0으로 변경합니다.(이미 존재하지 않는 물고기)

최대값을 업데이트 한 후 물고기를 이동시킵니다.

def move_shark(board, fishes, res, x, y, depth):
    num = board[x][y][0]
    res += num
    d = board[x][y][1]
    board[x][y] = -1
    fishes[num] = 0
    global ans
    ans = max(ans, res)
    move_fish(board, fishes)
    board[x][y] = 0

 

물고기가 이동한 후 상어가 이동할 수 있는 모든곳에 하나씩 상어를 이동시켜 값을 확인합니다.

for _ in range(4):
    x, y = dx[d] + x, dy[d] + y
    if 0 <= x < 4 and 0 <= y < 4:
        if board[x][y] != 0:
            move_shark(deepcopy(board), deepcopy(fishes), res, x, y, depth + 1)

 

함수를 실행시킨 후 답을 출력하면 됩니다.

ans = 0
move_shark(board, fishes, 0, 0, 0, 0)
print(ans)

 

물고기의 움직임을 구현하는 함수입니다.

1번부터 17번 까지 물고기가 존재한다면 물고기의 방향으로 이동가능한지 살핀 후 물고기를 이동시킵니다.

만약 불가능하다면 물고기를 회전시켜 이동가능하면 이동시킵니다.

def move_fish(board, fishes):
    for i in range(1, 17):
        if fishes[i] == 0:
            continue
        else:
            x, y = fishes[i]
            d = board[x][y][1]
            for j in range(1, 9):
                nx, ny = dx[d] + x, dy[d] + y
                if 0 <= nx < 4 and 0 <= ny < 4:
                    if board[nx][ny] == 0:
                        board[x][y][1] = d
                        tmp = board[nx][ny]
                        board[nx][ny] = board[x][y]
                        board[x][y] = tmp
                        fishes[i] = [nx, ny]
                        break

                    elif board[nx][ny] != -1:
                        board[x][y][1] = d
                        new_fish = board[nx][ny][0]
                        tmp = fishes[i]
                        fishes[i] = fishes[new_fish]
                        fishes[new_fish] = tmp

                        tmp = board[nx][ny]
                        board[nx][ny] = board[x][y]
                        board[x][y] = tmp
                        break
                d = (d + 1) % 8

 

백준 19236 청소년 상어 Python 코드였습니다.

감사합니다.