[softeer] 함께하는 효도 - 파이썬

 

함께하는 효도 문제

https://softeer.ai/practice/7727

 

 

파이썬 정답코드

import sys
from itertools import product
# 한 명이 움직이는 모든 방향의 조합 : [(0~3), (0~3), (0~3)] -> 4^3 = 64
# 모든 인원의 움직이는 방향의 조합 : (64) ^ 3 = 263144

input = sys.stdin.readline
n, m = map(int,input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
start_positions = [list(map(int, input().split())) for _ in range(m)]

# 모든 경우의 수
t = 3 # 3초
paths = list(product(range(4),repeat=m*t))

dx = [0,0,1,-1] # 동서남북
dy = [1,-1,0,0]

max_value = 0
for path in paths:
    value = 0
    visited = [[0]*n for _ in range(n)]
    for i, sp in enumerate(start_positions):
        x, y = sp
        x, y = x-1, y-1
        
        # 시작 위치 방문처리 및 수확량 누적
        visited[x][y] = 1	
        value += graph[x][y]

        for j in path[i*t:(i+1)*t]:
            nx = x + dx[j]
            ny = y + dy[j]
            
            if 0<=nx<n and 0<=ny<n:		# 지도 밖을 안 나가는 경우만
                if visited[nx][ny] == 0:	# 방문하지 않은 곳만 수확량 누적
                    value += graph[nx][ny]	
                visited[nx][ny] = 1		# 방문처리
                x,y = nx, ny			# 현재 위치 갱신

    if max_value < value: 
    	max_value = value
        
print(max_value)

 

- 해설 

dfs 풀이는 헷갈려서, 브루트포스로 풀었다.

최대 3명일 때 움질일 수 있는 조합은 최대 263,144 조합이다. 각 조합에 대해 시뮬레이션을 진행했을 때, 지나간 자리의 value값을 누적하고, 각 조합의 누적값을 비교해서 최대값을 뽑아낸다.

 

- 시간복잡도 고려

paths의 최대 길이가 263,144이고,

start_positions 최대 길이는 최대 3명이므로 3이고,

t=3 이므로 3번 움직일 수 있으므로 263,144 * 3 * 3 = 2,368,296

위의 코드는 최대 2백만의 연산량을 갖는다.

 

- 추가해볼만한 테스트 케이스 

그리디 유형이 아니다. 루트가 겹치는 경우를 고려해서 짜야한다.

# 아래 테스트 케이스 통과해야함.
6 2
0 0 0 1 0 0 
0 0 0 1 0 0 
0 0 0 1 0 0 
0 0 1 1 1 1 
0 0 0 0 0 0 
0 0 0 0 0 0 
1 4
4 3

# 정답 7