SWEA - 최소합 (5188) [Python]

 문제

 

 

 문제 상황

 

- 오른쪽 또는 아래쪽으로만 움직이면서 합을 더해나가는 구조이다. 이 중 도착했을 때 총합이 최소가 되는 경로를 찾으면 된다.

 

 

 

 해결 전략

 

- 백트래킹 최소합 문제와 거의 비슷하다. 다만 N-queen처럼 단방향으로 움직이는 것이 아니라 2차원적으로 움직이므로 조금 다르지만 기본적으로 Pruning 하는 개념은 같다.

 

 

 

 코드

 

# 탐색 함수
def BFS(x, y):
    # 전역변수 선언
    global min_total, sub_sum
    # 더 계산할 필요가 없다.
    if min_total < sub_sum:
        return
    # x,y가 N-1, N-1 즉 목적지에 도달하면 종료
    if x == N-1 and y == N-1:
        if min_total > sub_sum:
            min_total = sub_sum
    # 아래, 오른쪽으로만 진행 가능
    dx, dy = [1,0], [0,1]
    for i in range(2):
        xx = x+dx[i]
        yy = y+dy[i]
        if 0<=xx<N and 0<=yy<N and not visited[xx][yy]:
            visited[xx][yy] = True
            sub_sum += maze[xx][yy]
            BFS(xx,yy)
            visited[xx][yy] = False
            sub_sum -= maze[xx][yy]
 
# testcase 입력받기
T = int(input())
for idx in range(T):
    N = int(input())
    maze = [list(map(int, input().split())) for _ in range(N)]
    # N의 최대값은 13이고 10 이하의 자연수 이므로 합이 260을 넘을 수 없다.
    min_total = 260
    # 부분합 계산
    sub_sum = maze[0][0]
    # 방문한 위치 체크
    visited = [[False for _ in range(N)] for i in range(N)]
    # 0,0에서 출발
    BFS(0,0)
    print(f"#{idx+1} {min_total}")

 

 

 해설

 

- 합을 전역변수로 설정하고 visited를 갱신해주며 pruning을 통해 탐색해주었다.

 

 새로 학습한 것 & 실수 

 

- 백트래킹 개념을 되집기 위해 풀어본 문제이다. SWEA에서 완전탐색으로 분류된 것과 전체 범위가 크지 않다는 것으로 보아 완전탐색으로 해결이 가능하겠지만 Pruning을 통해 전부 탐색하지는 않았다.

 

- 문제의 조건대로 할 때 시작점을 생각하지 않고 sub_sum을 0으로 시작하다보니 (0,0) 요소가 더해지지 않았다. 초기값을 (0,0)으로 변경하여 해결하였다.

 

출처 - https://swexpertacademy.com/main/