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

 

함께하는 효도 문제

https://softeer.ai/practice/7727

 

 

파이썬 정답코드

#[2024. 6. 28. 00:02] 문제 변경 전. 25년 기준 아래 코드 마지막 테스트 케이스 통과 x
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

 

 

- 2025.03.20 기준 - 

과거에 풀었던 문제가 문제 변경과 함께 테스트 케이스가 추가되었다.

추가된 케이스는 아래와 같은 경우이다. 아래 케이스가 통과한다면 아마 12번째 케이스도 통과할 것이다.

# 친구가 3초 때, 나의 시작위치로 와서 마무리 하는 경우.
2 2
1 1
1 1
1 1
2 1

 

#[2024. 6. 28. 00:02] 문제 변경 전. 25년 기준 아래 코드 마지막 테스트 케이스 통과 x
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
        
        # 시작 위치 방문처리 및 수확량 누적 -> 마지막에 다른 친구의 시작위치로 오면 겹칠 수 있다.
        if visited[x][y] == 0: 
            value += graph[x][y] 
        visited[x][y] = 1

        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)

이 코드는 기존 코드에서 조금만 수정한 코드이다. 무사 통과했다. 

기존 코드에서는 3초 때 친구의 시작위치로 오는 경우를 배제했다. 그래서 테스트 케이스 12에서 틀린 것 같다.

 

참고로,

문제조건에서 변경된 내용인 '이때, 친구들끼리 이동하는 도중 동시에 같은 사과나무에서 마주치는 경우에는 싸움이 일어날 수 있기 때문에 남우는 이와 같은 경우가 없기를 바랍니다.' 는 위 코드에선 의미 없는 내용이다.

즉, 동시에 같은 위치에서 마주쳐야지만 수확량이 최대를 찍는 케이스는 존재하지 않는다.

코드를 바꿀 때 동시에 마주치는 케이스를 제외해줘야 하는건가? 라는 생각에 아래와 같이 코드를 짰는데, 마찬가지로 통과는 하지만, 동시에 같은 위치에서 마주치는 경우이면서 수확량이 가장 높게 나오는 경우는 애초에 불가하다.

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
        
        if visited[x][y] == 0: # 마지막에 다른 친구의 시작위치로 오면 겹칠 수 있다.
            value += graph[x][y] 
        visited[x][y] = 1
        
        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] == visited[x][y] + 1: # 동시에 같은 위치에 오는 경우
                    value = -1
                    break
                if visited[nx][ny] == 0:
                    value += graph[nx][ny]
                visited[nx][ny] = visited[x][y] + 1
                x,y = nx, ny
        # print(value)
        if value == -1:
            break
        
    if max_value < value: 
        max_value = value
print(max_value)