1. 문제

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

2. 풀이

삼성 SW 역량테스트 문제입니다. 물고기가 움직이는 공간은 물고기가 있는 공간만 가능하다고 착각하여 시간이 너무 오래 소요된 문제였습니다. 상어가 어디로 이동할 지 모르기 때문에, dfs 를 이용하여 모든 경우의 수를 구하여 정답을 구하면 됩니다.

~~~python import copy dr = [-1, -1, 0, 1, 1, 1, 0, -1] dc = [ 0, -1, -1, -1, 0, 1, 1, 1] N = 4 maps = [[] for _ in range(N)] ate_fish = 0 shark_loca = [0, 0] shark_way = -1 max_ate_fish = 0 for i in range(N): a = list(map(int, input().split())) for j in range(N): maps[i].append([a[2j], a[2j+1]-1])

def find_fish(fish_num): for r in range(N): for c in range(N): if maps[r][c][0] == fish_num: return r, c return -1, -1

물고기가 움직이는 동작 구현

def fishes_move(): for fish_num in range(1, N*N+1): row, col = find_fish(fish_num) way = maps[row][col][1] if row == -1 or col == -1: continue

    for w_i in range(0, 8+1):
        n_way = (way+w_i)%8
        n_row = row + dr[n_way]
        n_col = col + dc[n_way]
        if n_row < 0 or n_row >= N or n_col < 0 or n_col >= N or [n_row, n_col] == shark_loca:
            continue
        # 물고기 찾아서 switch
        maps[row][col] = [fish_num, n_way]
        maps[row][col], maps[n_row][n_col] = maps[n_row][n_col], maps[row][col]
        break

상어가 갈 수 있는 공간 리턴

def find_shark_can_go(): shark_go_list = [] for dist in range(1, 5): n_row = shark_loca[0] + dr[shark_way]dist n_col = shark_loca[1] + dc[shark_way]dist if n_row < 0 or n_row >= N or n_col < 0 or n_col >= N or maps[n_row][n_col][0] <= 0: continue shark_go_list.append([n_row, n_col]) return shark_go_list

상어 이동 dfs 구현

def shark_move(): global shark_way, shark_loca, max_ate_fish, ate_fish, maps fishes_move() # 갈 수 있는 영역 찾아내기 shark_go_list = find_shark_can_go()

if len(shark_go_list) == 0:
    max_ate_fish = max(max_ate_fish, ate_fish)
    return

# 갈 수 있는 영역을 대상으로 dfs
for next_shark in shark_go_list:
    # 다음 dfs 를 위한 값 변경
    before_map = copy.deepcopy(maps)
    eated_fish = [maps[next_shark[0]][next_shark[1]][0], maps[next_shark[0]][next_shark[1]][1]]
    sub_shark_loca = shark_loca
    sub_shark_way = shark_way

    maps[next_shark[0]][next_shark[1]] = [-1, -1]
    shark_loca = next_shark
    shark_way = eated_fish[1]
    ate_fish += eated_fish[0]

    shark_move()

    # 변경한 값 원래대로 되돌리기 
    shark_loca = sub_shark_loca
    shark_way = sub_shark_way
    ate_fish -= eated_fish[0]
    maps = before_map
return 1

ate_fish, shark_way = maps[0][0] maps[0][0] = [-1,-1] shark_move() print(max_ate_fish) ~~~c