[SW Expert Academy] 최소합

💡 문제

그림처럼 NxN 칸에 숫자가 적힌 판이 주어지고, 각 칸에서는 오른쪽이나 아래로만 이동할 수 있다.

맨 왼쪽 위에서 오른쪽 아래까지 이동할 때, 지나는 칸에 써진 숫자의 합계가 최소가 되도록 움직였다면 이때의 합계가 얼마인지 출력하는 프로그램을 만드시오.

1	2	3
2	3	4
3	4	5

그림의 경우 1, 2, 3, 4, 5순으로 움직이고 최소합계는 15가 된다. 가능한 모든 경로에 대해 합을 계산한 다음 최소값을 찾아도 된다.

[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 첫 줄에 가로 세로 칸 수 N이 주어지고, 다음 줄부터 N개씩 N개의 줄에 걸쳐 10이하의 자연수가 주어진다. 3<=N<=13

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

💡 문제 풀이

dfs로 풀이를 하려 했었지만, 이런 문제는 대부분 dfs로 풀어보았기 때문에 bfs로 한번 해보았습니다.

1. 좌, 우, 아래, 위 방향을 지정하기 위해 dx, dy를 선언합니다.
2. [0, 0] 에서 시작합니다.
3. queue에 저장된 좌표 값을 받아옵니다.
4. 현재 좌표 기준 네 방향으로 진행합니다.
5. 갈 수 있거나, 이미 방문한 곳이 아니라면 진행합니다.
6. 5번 조건에서 만약 방문한 곳으로 진행할 때 현재 값에서 진행한 수가 더 작다면 수를 바꿔줍니다.

💡 코드

from collections import deque
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
   
    N = int(input())
    arr = []
    q = deque()

    for i in range(N):
        arr.append(list(map(int, input().split())))

    check = [[0 for _ in range(N)] for _ in range(N)]
    dist = [[0 for _ in range(N)] for _ in range(N)]

    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    dist[0][0] = arr[0][0]
    q.append([0, 0])

    while q:
        posY, posX = q.popleft()

        for i in range(4):        
            nextX = posX + dx[i]
            nextY = posY + dy[i]

            if nextX < 0 or nextY < 0 or nextX >= N or nextY >= N:
                continue
            cdist = arr[nextY][nextX] + dist[posY][posX]
            if check[nextY][nextX] == 1 and cdist < dist[nextY][nextX]: # 현재 칸에서 다음칸으로 진행한 값이 원래 있던 값보다 작다면 바꿈.``
                dist[nextY][nextX] = cdist
                q.append([nextY, nextX])
                continue

            if check[nextY][nextX]:
                continue

            check[nextY][nextX] = 1
            q.append([nextY, nextX])
            dist[nextY][nextX] = cdist

    print(f'#{test_case} {dist[N-1][N-1]}')