[BOJ][Python] 백준 19236번: 청소년 상어

1일 1PS 45일차!

📚 문제

---

골드 2

• DFS
• 단순 구현 문제로 볼 수 있다.

💡 풀이 과정

---

• 8가지 방향에 대해서 dx, dy 를 설정한다.
• DFS 를 수행하면서 물고기 이동, 상어의 이동을 각각 구현한다.
  • 물고기 이동은 작은 번호부터 하나하나 찾아가면서 이동시킨다.
  • 방향 변경에 대해서도 모두 진행해준다.
  • 상어의 이동은 1칸 ~ 3칸에 대해서 물고기가 있는 경우에 대해서 dfs 를 진행한다.

📌포인트

---

• 완전 탐색
  • 4 * 4 로 그 수가 적기에 완전 탐색해도 무리가 없다.

💻 코드

---

import copy


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):
        fx, fy = -1, -1
        for x in range(4):
            for y in range(4):
                if board[x][y][0] == f:
                    fx, fy = x, y
                    break
        if fx == -1 and fy == -1:
            continue

        fd = board[fx][fy][1]

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

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


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):
    line = list(map(int, input().split()))
    temp = []
    for j in range(4):
        temp.append([line[2 * j], line[2 * j + 1] - 1])
    board[i] = temp

max_score = 0

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