문제

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

풀이

조건

• 한 칸에는 물고기가 한 마리 존재한다.
• 각 물고기는 번호와 방향을 가지고 있다.
• 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다.
• 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.
• 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다.
  • 첫 시작
• 이후 물고기가 이동한다.
  • 물고기는 번호가 작은 물고기부터 순서대로 이동한다.
  • 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다.
  • 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다.
    • 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다.
    • 그 외의 경우에는 그 칸으로 이동을 한다.
  • 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.
• 물고기의 이동이 모두 끝나면 상어가 이동한다.
  • 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다.
    • 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다.
  • 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다.
  • 물고기가 없는 칸으로는 이동할 수 없다.
  • 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다.
    • 이게 종료 조건
• 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

풀이 순서

• 위의 조건 순서대로 코드를 작성한다.
• 상어가 이동할 수 있는 여러 자리 중 한 자리를 골라 이동하는데 그렇게 했을 때 먹은 물고기 번호의 합이 가장 큰 경우를 찾는 문제이다.
• 이는 DFS를 사용해 구현해야한다.

코드

Python

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

    # 물고기 움직임
    # 물고기 1번부터 16번까지 찾기
    for f in range(1, 17):
        f_x, f_y = -1, -1
        # board 뒤져서 찾기
        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] # 상어 방향
    # 최대 4번까지 현재 방향의 자리 탐색 가능
    for i in range(1, 5):
        nx = sx + dx[s_d] * i
        ny = sy + dy[s_d] * i
        # 이동 가능한 자리인지 체크한 뒤 dfs
        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)

정리

• DFS를 사용하는 부분은 구현했지만 물고기 번호가 작은 순서대로 이동한다는 부분에서 어려움을 겪었다.
• 처음에는 heapq를 사용해 물고기 번호가 작은 순서대로 정렬해 이동시키려고 했다.
  • 매번 작은 번호의 물고기를 완전탐색 하는 부분이 시간을 많이 낭비한다고 생각했다.
• heapq를 사용하니 상어에게 먹힌 물고기를 제거해주는 부분에서 어려움을 느꼈고 완전탐색으로 물고기 번호 순서대로 이동하도록 해 해결했다.