[SWEA] 최소합 (python)

SWEA의 LEARN - Course의 완전 검색 3차시의 최소합 문제

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYDrI61lYDFAVT 

SW Expert Academy

최소합 문제

왼쪽 위 모서리에서 출발해서 → 혹은 ↓로 이동해서 오른쪽 아래 모서리 까지 이동했을 경우, 해당 칸의 합계가 최소가 되도록 이동했을 때의 최소 값을 구하는 문제

완전 탐색을 이용할 수 있다.

⚙️내가 푼 정답코드

def find(y,x): # 찾기
    global result, temp # 결과 값과 임시 값
    if result < temp: # 임시 값이 결과 값을 넘어버리면
        return # 끝

    if x == N-1 and y == N-1: # 목적지에 도착했으면
        result = temp # 결과 값에 임시 값을 반환
        return

    for dy, dx in move: # 오른쪽 아래쪽 탐색 탐색
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            temp += board[ny][nx] # 값 넣어서
            find(ny,nx) # 뒤져 보고
            temp -= board[ny][nx] # 아니면 돌아오자

T = int(input())
for case in range(1,T+1):
    move = [[1,0],[0,1]]
    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]
    result = float('inf')
    temp = board[0][0] # 0,0 부터시작
    find(0,0)
    print(f'#{case} {result}')

📌문제 접근 포인트

1. (0,0)에서부터 이동을 시작할 때, 오른쪽과 왼쪽으로 이동 했을 경우 찾을 수 있는 모든 경우의 수를 체크해보자.
2. 먼저 이동하면서 체크할 임시 값과, 목척지에 도착했을 때의 결과 값 2가지를 생각해보자.
3. 만약 결과 값에 저장된 값을 임시 값이 초과하면 최소값으로 볼 수 없으니 끝내버리고, 다시 탐색을 반복하도록 하자
4. 모든 경우를 탐색해 나가도록 코드를 작성하면 완성