[SWEA] 5188_최소합

📕 문제

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

💡 풀이법

1. dfs 함수를 만들어서 한칸씩 앞으로 전진해나간다.

2. 이 경우에는 맨 왼쪽 위에서 맨 오른쪽 아래칸으로 이동해야하고 중간에 가로막는 벽 같은 것도 없기 때문에 방향을 (0, 1), (1, 0) 으로만 설정한다.

(되돌아가지 않기 때문에 방문 처리 또한 필요없다)

3. 한칸씩 갈 수록 그 곳에 해당되는 숫자를 더해가며 재귀 dfs를 실행한다.

4. 만약 중간에 최소합(ans)보다 커지게 된다면 return한다. (가지치기)

5. 도착지에 도착하면 지금까지의 경로를 더한 s와 ans와 비교하여 s가 더 작으면 ans를 s로 바꿔준다.

 

dxy = [(0,1),(1,0)]
def dfs(x, y, s):
    global ans

    if s >= ans:  # 가지치기
        return

    if x == N-1 and y == N-1:  # 도착지에 도착한 경우
        if s < ans:
            ans = s
        return

    for dx, dy in dxy:
        nx, ny = x + dx, y + dy

        if nx > -1 and nx < N and ny > -1 and ny < N:
            dfs(nx, ny, s+matrix[nx][ny])

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    matrix = [list(map(int, input().split())) for _ in range(N)]
    ans = 999999
    dfs(0, 0, matrix[0][0])
    print('#{} {}'.format(tc, ans))