[Softeer] 함께하는 효도

문제

요약

n*n크기의 땅에서 m명의 친구들이 3초의 시간동안 농작물을 수확할때 수확할 수 있는 최대 농작물의 수는?

친구들이 서있는 위치의 농작물은 0초에 수확한다.

친구들 간에 도중에 만날 수는 있지만 한명만 수확한 것으로 친다.

 

원본

https://softeer.ai/practice/7727

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

 

풀이

풀이1(오답)

 

일단 접근 방식이 맞았다는 사실에 나자신 칭찬해 ㅠㅜㅠ

 

새로 알게 된 것 첫번째는 permutations으로 친구들의 순서를 바꿔줘야 한다는 점

한친구가 먼저 최대 수확량인 곳으로 움직이면 다른 친구가 그것보다 더 많이 먹을 수 있지 않나? 라고 생각만 하고

그럼 이걸 어떻게 확인하지? 싶었는데

친구들의 수가 최대 세명이기 때문에 permutations을 돌려도 시간초과 없이 확인할 수 있다.

 

하지만 이 풀이에도 틀린부분이 있다. 어딜까요오~~?

import sys
from collections import deque
from itertools import permutations
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*n for _ in range(n)]

stack = []
for i in range(m):
    x, y = map(int, input().split())
    stack.append((x-1, y-1))

d = [(-1,0), (1,0), (0,-1), (0,1)]
answer = 0

def solve(x, y, i, cnt, value):
    global answer
    
    if cnt == 4:
        if i == m-1:
            answer = max(answer, value)
        else:
            solve(stack[s[i+1]][0], stack[s[i+1]][1], i+1, 0, value)
        return

    value += arr[x][y]
    
    for dx, dy in d:
        nx, ny = x+dx, y+dy
        if 0<=nx<n and 0<=ny<n and visited[nx][ny] == 0:
            visited[nx][ny] = 1
            solve(nx, ny, i, cnt+1, value)
            visited[nx][ny] = 0

for s in permutations([a for a in range(m)]):
    x, y = stack[s[0]]
    solve(x, y, 0, 0, 0)
    
print(answer)

 

 

풀이2(정답)

 

일단 cnt == 3일때 까지만 확인해야 한다는 것을 디버깅을 통해서 알았다.

cnt == 4일때까지 돌리면 5개 지점을 확인하게 된다.

 

그리고 else 문에서 다음 친구로 넘어갈 때, 그 친구가 서있는 자리의 농작물 수를 더해주어야 한다.

이것도 디버깅 하면서 알게 됐다.

알고리즘 할때, 꼭 디버깅 하면서 확인하기!!

import sys
from collections import deque
from itertools import permutations
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*n for _ in range(n)]

stack = []
for i in range(m):
    x, y = map(int, input().split())
    stack.append((x-1, y-1))
    visited[x-1][y-1] = i+1

d = [(0,1), (-1,0), (1,0), (0,-1)]
answer = 0

def solve(x, y, i, cnt, value):
    global answer, visited
    # 한사람이 3초 모두 이동
    if cnt == 3:
        # 마지막 사람까지 모두 이동
        if i == m-1:
            # 값 갱신
            answer = max(answer, value)
        # 마지막 사람이 아니면 다음 사람 움직이기
        else:
            x, y = stack[s[i+1]]
            solve(x, y, i+1, 0, value+arr[x][y])
        return

    for dx, dy in d:
        nx, ny = x+dx, y+dy
        # 이동
        if 0<=nx<n and 0<=ny<n and visited[nx][ny] == 0:
            # 방문표시
            visited[nx][ny] = i+1
            solve(nx, ny, i, cnt+1, value+arr[nx][ny])
            visited[nx][ny] = 0
    # 이동할 곳이 없다면(모두 수확했거나 사람들이 다 차있으면) 바로 그 상태로 수확 종료
    else: solve(x, y, i, 3, value)

# 움직이는 순서 바꿈.
for s in permutations([a for a in range(m)]):
    x, y = stack[s[0]]
    solve(x, y, 0, 0, arr[x][y])
  
print(answer)

 

이걸 문제에서 준 조건을 하나하나 생각하면서 맞춰가면 빠르게 풀 수 있을 것 같은데

아직 결정력이 조금 부족한 것 같다.

 

그래도 잘 고쳐서 뿌듯 :)