이거 풀고 골3 되엇읍니다...

문제 링크

19236 - 청소년 상어

문제 설명

4*4 크기의 격자 공간 각 칸에 물고기가 존재한다. 물고기는 1~16 사이의 유일한 번호를 갖고, 상하좌우 대각선 8개의 방향을 갖는다.
상어는 초기에 (0,0)에 들어와서 물고기를 먹고, (0,0)에 있던 물고기의 방향을 바라본다.

이동은 다음과 같은 순서로 진행된다.

1. 물고기의 이동
   : 번호가 작은 물고기 순서대로 바라보는 방향으로 한칸 이동한다. 이때, 물고기는 상어가 있거나 격자를 벗어나는 칸으로의 이동은 불가능하다. 바라보는 방향이 빈칸이면 한칸 이동, 다른 물고기가 있는 칸이면 그 물고기와 위치를 교환한다. 이동할 수 있는 칸을 찾을때까지 45도 반시계방향 회전하고, 한바퀴 다 돌았는데 이동할 칸이 없으면 이동하지 않는다.
2. 상어의 이동
   물고기의 이동이 끝나면 상어가 이동한다. 바라보는 방향의 여러 칸 중 물고기가 있는 칸으로 N칸 이동이 가능하다. 이동중에 지나치는 물고기는 먹지 않고, 도착칸에 있는 물고기를 먹고 해당 물고기가 바라봤던 방향을 바라본다.

위와 같이 이동할때 상어가 먹을 수 있는 물고기 번호의 최대값은?

문제 풀이

처음에 생각을 잘못해서 한 30분 헤맨거같다 %^^ ; 완전탐색해서 최대값을 찾아야 하므로 dfs를 이용해서 풀이했다.

일단 전체 격자, 물고기, 상어는 다음과 같이 저장했다.

board[i][j] : (i,j)칸의 상태 -> 1: 빈칸, 0: 상어, 나머지: 물고기 번호
fishes[i] : i번 물고기의 [행, 열, 방향, 먹혔는지?] -> 먹혔는지의 판단을 dictionary에서 지우기보다 그냥 플래그로 줌
shark = [i,j] : 상어의 현재 위치

전체적인 흐름은 다음과 같다.

1. 상어의 초기 상태
   : (0,0)의 물고기를 먹고, (0,0)에 위치 & 그 칸에 있던 물고기가 바라보던 방향으로 갱신
2. dfs로 모든 경우 탐색
   2.1 물고기 이동시키기
   : 번호가 작은 물고기부터 8방향에 대해서 검사 & 이동
   2.2 상어 이동시키기
   : 1칸부터 벽을 만날때까지의 칸중에 물고기가 있으면 dfs 재귀적으로 호출

물고기 이동

물고기가 이동하는 함수는 다음과 같이 구현했다.
dictionary의 key값인 물고기 번호를 오름차순으로 정렬
-> 각 물고기마다 이번 turn에 살아있는 물고기면
-> 8방향을 돌면서 이동 가능한 칸 찾기

def move_fishes(board, fishes):
    c_board = copy.deepcopy(board)
    cur_fish = sorted(fishes.keys())

    for f in cur_fish:
        x, y, d, flag = fishes[f]
        # 이번 turn에 살아있는 물고기면
        if flag == True:
            for i in range(8):
                nx, ny = x+dx[d-1], y+dy[d-1]
                if in_bound(nx, ny) and c_board[nx][ny] != 0:
                    # 범위 안이고 상어있는 칸이 아니면
                    if c_board[nx][ny] == -1:
                        # 빈칸이면 그냥 이동
                        c_board[nx][ny] = f
                        c_board[x][y] = -1
                        fishes[f][0], fishes[f][1], fishes[f][2] = nx, ny, d
                        break
                    else:
                        # 빈칸이 아니면 교환
                        n_f = c_board[nx][ny]
                        c_board[nx][ny] = f
                        c_board[x][y] = n_f
                        fishes[f][0], fishes[f][1], fishes[f][2] = nx, ny, d
                        fishes[n_f][0], fishes[n_f][1] = x, y
                        break
                else:
                    d = (d+1)%8
    return c_board

dfs

재귀적으로 최대값을 찾는 함수는 다음과 같다.

def dfs(board, shark, fishes, count):
    global answer

    # 1. 물고기의 이동
    n_fishes = copy.deepcopy(fishes)
    c_board = move_fishes(board, n_fishes)

    # 2. 상어 이동
    x, y, d = shark
    while True:
        nx, ny = x+dx[d-1], y+dy[d-1]
        if not in_bound(nx, ny):
            break
        
        if c_board[nx][ny] != -1:
            # 빈칸이 아니면 물고기 먹고 그 칸으로 이동
            f_n = c_board[nx][ny]
            n_fishes[f_n][3] = False
            c_board[nx][ny] = 0
            c_board[shark[0]][shark[1]] = -1
            # 이 상태에 대해서 dfs
            dfs(c_board, [nx, ny, n_fishes[f_n][2]], n_fishes, count+f_n)
            c_board[shark[0]][shark[1]] = 0
            c_board[nx][ny] = f_n
            n_fishes[f_n][3] = True

        x, y = nx, ny
                
    answer = max(answer, count)

전체 코드

import sys
from collections import defaultdict
import copy

input = sys.stdin.readline
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]
# -1: 빈칸, 0: 상어, 나머지: 물고기 번호
board = [[-1 for _ in range(4)] for _ in range(4)]
fishes = defaultdict()
shark = [0,0]
answer = 0

for i in range(4):
    tmp = list(map(int, input().split()))
    for j in range(4):
        n, d = tmp[2*j], tmp[2*j+1]
        fishes[n] = [i,j,d, True]
        board[i][j] = n
        if i==0 and j==0:
            shark.append(d)
            answer = n

# 상어의 초기 이동
del(fishes[board[0][0]])
board[0][0] = 0

def in_bound(x, y):
    if x in range(4) and y in range(4):
        return True
    return False

def move_fishes(board, fishes):
    c_board = copy.deepcopy(board)
    cur_fish = sorted(fishes.keys())

    for f in cur_fish:
        x, y, d, flag = fishes[f]
        # 이번 turn에 살아있는 물고기면
        if flag == True:
            for i in range(8):
                nx, ny = x+dx[d-1], y+dy[d-1]
                if in_bound(nx, ny) and c_board[nx][ny] != 0:
                    # 범위 안이고 상어있는 칸이 아니면
                    if c_board[nx][ny] == -1:
                        # 빈칸이면 그냥 이동
                        c_board[nx][ny] = f
                        c_board[x][y] = -1
                        fishes[f][0], fishes[f][1], fishes[f][2] = nx, ny, d
                        break
                    else:
                        # 빈칸이 아니면 교환
                        n_f = c_board[nx][ny]
                        c_board[nx][ny] = f
                        c_board[x][y] = n_f
                        fishes[f][0], fishes[f][1], fishes[f][2] = nx, ny, d
                        fishes[n_f][0], fishes[n_f][1] = x, y
                        break
                else:
                    d = (d+1)%8
    return c_board

def dfs(board, shark, fishes, count):
    global answer

    # 1. 물고기의 이동
    n_fishes = copy.deepcopy(fishes)
    c_board = move_fishes(board, n_fishes)

    # 2. 상어 이동
    x, y, d = shark
    while True:
        nx, ny = x+dx[d-1], y+dy[d-1]
        if not in_bound(nx, ny):
            break
        
        if c_board[nx][ny] != -1:
            # 빈칸이 아니면 물고기 먹고 그 칸으로 이동
            f_n = c_board[nx][ny]
            n_fishes[f_n][3] = False
            c_board[nx][ny] = 0
            c_board[shark[0]][shark[1]] = -1
            dfs(c_board, [nx, ny, n_fishes[f_n][2]], n_fishes, count+f_n)
            c_board[shark[0]][shark[1]] = 0
            c_board[nx][ny] = f_n
            n_fishes[f_n][3] = True

        x, y = nx, ny
                
    answer = max(answer, count)

dfs(board, shark, fishes, answer)
print(answer)

소요 시간

2시간
deepcopy 안써보려고 이리저리 해봤는데 삽질만 30분함 ^_ㅋ,,