1249. [S/W 문제해결 응용] 4일차 - 보급로 (삼성 SW Academy, C++)

풀이 과정

 

 arr에 map을 입력 받고, 시작점인 (0, 0)부터 탐색을 시작합니다. 해당 칸까지 이동하였을 때, 걸린 최소 비용을 dist 배열에 저장해 줍니다. dist 배열은 매우 큰 수로 초기값을 정해 줍니다. 

 

 간단한 예를 들어, dist에 파란색 경로의 최소 비용이 저장되어 있을 때, 주황색 경로의 최소 비용이 더 작은 경우 dist에 저장된 값을 주황색 경로의 값으로 갱신하여 줍니다. 따라서 탐색이 종료되면, dist[n-1][n-1]에는 (n-1, n-1)까지 가는 최소 비용이 저장되어 있게 됩니다.

 

 

코드

 

#include <cstdio>
#include <queue>
using namespace std;
 
int n;
int arr[100][100], dist[100][100];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
void search()
{
    queue <pair<int, int>> q;
    q.push(make_pair(0, 0));
 
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx < n && ny < n && nx >= 0 && ny >= 0)
            {
                int ndist = arr[nx][ny] + dist[x][y];
                if (ndist < dist[nx][ny])
                {
                    q.push(make_pair(nx, ny));
                    dist[nx][ny] = ndist;
                }
            }
        }
    }
    return;
}
 
int main(){
 
    int t;
    scanf("%d", &t);
 
    for (int tc = 1; tc <= t; tc++)
    {
        scanf("%d", &n);
 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                scanf("%1d", &arr[i][j]);
                dist[i][j] = 99999999;
            }
 
        dist[0][0] = 0;
        search();
 
        printf("#%d %d\n", tc, dist[n-1][n-1]);
    }
 
    return 0;
}

 

 

제출 결과

 

 

 

문제 출처

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&&&

SW Expert Academy