문제 풀이

사람이 m 명일 때 수확량 최댓값을 구해야 한다. (단 이미 다른 사람이 방문했으면 그 구역 수확량은 0 임)

m 명을 동시에 돌려서 수확량 최댓값 구하기

하는 방법을 모르겠어서 패스 (재귀로 푸는 것 같다.)

한 명씩 최대값 수확해서 최대값 구하기 (내가 한 풀이)

누가 먼저 수확하냐에 따라서도 최댓값이 변경되기 때문에 여러 케이스 확인 필요함
이전 사람이 밟은 구역에 대해서 기록을 해놔야 이후 사람의 최댓값을 구할 수 있음

코드

import sys
from itertools import permutations  # 누가 먼저 밟는지에 따라 달라지므로 그 순서를 정하기 위해 사용함
from collections import deque       # 최대수확량을 BFS로 찾기 위해 사용

input = sys.stdin.readline

def bfs(start):
    start_x, start_y = start
    start_x -= 1
    start_y -= 1
    # 스택에는 좌표값과, 움직인 횟수, 수확량, 밟은 좌표를 리스트화해서 넣는다.
    stack = deque([[start_x, start_y, 0, n_array[start_x][start_y], [[start_x, start_y]]]])
    # 최대 수확량과 그 경우 움직인 좌표를 기억할 곳 
    bfs_max = 0
    fast_route = []
    # 방향계
    direction_x = [0,0,-1,1]
    direction_y = [1,-1,0,0]
    while stack:
        x, y, cnt, bfs_sum, before_route = stack.popleft()
        # 3번 움직였을때
        if cnt == 3:
            if bfs_max < bfs_sum:
                bfs_max = bfs_sum
                fast_route = before_route
        # 3번 이상 움직인 것은 스택에 담지 않을 것
        if cnt > 3: continue
        for dir in range(4):
            new_x = x + direction_x[dir]
            new_y = y + direction_y[dir]
            # array에 없는 좌표 패스
            if not 0 <= new_x < n or not 0 <= new_y < n : continue
            # 수확하는 중인 사람이 이전 방문했던 곳이라면 다시 가지 않음
            if [new_x, new_y] in before_route: continue
            # 이전 사람이 방문하였던 구역이면
            if visited[new_x][new_y]:
                new_bfs_sum = bfs_sum  # 아무것도 더하지 않는다.
            else: # 새 구역이면 더하기
                new_bfs_sum = bfs_sum + n_array[new_x][new_y]
            # 이전 좌표 기억할 새 리스트 만들기 / 얕은 복사를 방지하기 위함
            new_before_route = []
            for route_info in before_route:
                new_before_route.append(route_info)
            new_before_route.append([new_x, new_y])

            stack.append([new_x, new_y, cnt + 1, new_bfs_sum, new_before_route])

    return bfs_max, fast_route  # 이 사람의 최대 수확량과 그 당시 밟은 루트 반환


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

m_time = []
for i in range(m):
    m_time.append(i)

max_sum = 0
# 밟는 순서, 순열로
for case in permutations(m_time):
    summed = 0 # 이 집합에서 최대 수확량
    visited = [[0] * n for _ in range(n)] # 먼저번 사람이 다녀갔는지 확인용
    for person in case:  # 순열 집합에 따라 한명씩 방문
        case_max_sum, route = bfs(m_list[person])
        summed += case_max_sum  # 현재 조합에서 최대값 수확량 넣기
        for x, y in route:      # 이전 사람이 밟은 좌표 기억하기
            visited[x][y] = 1
    # 이 집합으로 만들어진 합이 이전보다 컸으면
    if max_sum < summed:
        max_sum = summed
print(max_sum)

아쉬운 점

너무 길다.. 재귀로 푼 것을 보니, 엄청 짧고 깔끔해서 따라 하고 싶은데 이해가 안돼서 엄두가 안 남
좀 더 높은 난이도였으면 런타임에러 각
- 최대 사람 수와 움직이는 횟수가 적어서 가능했던 풀이라고 생각이 든다.

배운 점

메모이제이션 잘 사용 못했는데, 필요에 의해서 습득하게 되었다. 이제 잘 활용할 수 있을 것 같다.
- BFS로 최대 수확량뿐만 아니라 그렇게 움직였을 때의 경로를 받아올 수 있는 방법은 없을까? 에 대한 대답이 됨
런타임 에러를 꺼려하지 않고 한번 해보는 것도 중요함
- 솔직히 짧은 코드면 모를까 긴 코드는 괜히 했다가 안되면 시험 시간이 부족할 수 있다고 생각했는데, 아예 안 하는 것보단 낫기는 함
- 내 생각보다 실행시간이 많이 빠르게 나와서 좋았다. testcase 평균 0.12초 밖에 안될 줄은 몰랐다.

수정 고민 점

더 짧게 못 수정할까?

- 사람 명수에 맞는 리스트 (m_time) 만들 때/ 왠지 할 때는 기억이 안 났다.

m = 3
# before
m_time = []
for i in range(m):
    m_time.append(i)
# after 
m_time = [i for i in range(m)]

- route 기억 시 얕은 복사 방지한 부분/ [[]]이중으로 감싸면 + 활용이 가능한지 몰랐다. []만 시도해 봐서 안 되는 줄 알았다..

# before
new_before_route = []
for route_info in before_route:
    new_before_route.append(route_info)
new_before_route.append([new_x, new_y])

# after
new_before_route = before_route + [[new_x, new_y]]

코드가 길어져서 배제한 부분
- bfs에서 stack에 시작좌표의 수확량을 넣는데 이전 사람이 이미 수확했으면 0을 넣어야 한다.
  - 사실 제출 전에 발견한 미스였는데, 그냥 지쳐서 제출했는데 없이도 통과됐다..
    - 없어도 되는 부분이 맞을까?