[소프티어 7727번] 함께하는 효도

Softeer - 현대자동차그룹 SW인재확보플랫폼

import sys

input = sys.stdin.readline

# m명의 친구를 불러 나무에서 열매를 수확
# n x n 크기의 격자에 모든 칸에 나무가 심어져있고, 각 나무마다 가능한 열매 수확량이 주어져 있음

# 친구들은 서로 다른 위치에서 출발하여 1초에 1칸씩 상하좌우로 움직임
# 최종적으로 모든 열매 수확량의 합을 최대로 만들고자 함

# 한 나무에 여러 친구가 방문하게 되더라도 열매는 딱 한번만 수확 가능
# 또한, 친구들끼리 이동하는 도중 만나는 것도 가능

# m명의 친구들이 3초동안 최대로 얻을 수 있는 열매 수확량의 총합

n, m = map(int,input().split())

area = [list(map(int,input().split())) for _ in range(n)]

start_coor = [tuple(map(int,input().split())) for _ in range(m)]
start_coor = [(x-1,y-1) for x,y in start_coor]

visited = [False]*m

dx, dy = [-1,1,0,0], [0,0,-1,1]

total = 0

answer = float("-inf")

def dfs(x,y,depth,index):

    global total
    global visited
    global answer

    visited[index] = True

    value = area[x][y]
    total += value
    area[x][y] = 0 

    if depth == 4:

        if all(visited):
            answer = max(total, answer)
        
        for i, coors in enumerate(start_coor):
            if not visited[i]:
                dfs(coors[0],coors[1],1,i)
                
        visited[index] = False
        total -= value
        area[x][y] += value
        
        return

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        if 0 <= nx < n and 0 <= ny < n:
            dfs(nx,ny,depth+1,index)

    visited[index] = False
    total -= value
    area[x][y] += value
            
dfs(start_coor[0][0],start_coor[0][1],1,0)

print(answer)

 

이번 문제는 총 m명의 친구들이 각 시작점에서 출발하여 3초간 움직일 수 있을 때 열매를 수확할 수 있는 최댓값을 구하는 문제이다.

 

먼저 최댓값을 구하기 위해서는 각 친구들이 움직일 수 있는 모든 경우의 수를 확인해야 했고, 따라서 DFS 알고리즘을 선택하게 되었다.

 

친구들을 한명씩 3초간 움직이게 만든 뒤 모든 친구들이 방문을 마무리하면(if all(visited)) 정답을 업데이트하는 방식으로 풀이하였다.