1249. [S/W 문제해결 응용] 4일차 - 보급로

문제

SW Expert Academy

S에서 시작해서 G까지 가는데 상하좌우 이동할 수 있다.

최소비용을 구하는 문제이다.

처음에는 bfs로 최소비용을 구하였지만, 지나온 경로를 체크하는 부분에서 의미가 없다고 생각해 풀지 못하였다.

이 문제는 최소 경로가 아니라 길을 돌아가더라도 최소비용을 구해야하는 것이다.

다음으로는 DP로 접근하였다.

S에서 행 끝까지, 열 끝까지 누적합을 기준으로 dp를 진행하였다.

하지만 답이 틀려 다른 외부 사이트에서 영감을 얻었다.

단서는 bfs형태로 이동하면서 dp 형태로 푸는 것이다.

bfs형태로 하면 지나온 경로를 체크해야하는데 이를 하지 않고 계속해서 최소비용을 갱신하는것이다.

while (!q.empty())
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int xx = x + dx[i];
                int yy = y + dy[i];
                if (xx < 0 || yy < 0 || xx >= n || yy >= n)
                    continue;
                if (dp[xx][yy] > dp[x][y] + arr[xx][yy]) //dp 부분
                {
                    dp[xx][yy] = dp[x][y] + arr[xx][yy];
                    q.push({xx, yy});
                }
            }
        }

dp를 처음에 무한대로 초기화 한다.

위의 코드에서 dp부분이 만족하면 최소비용을 갱신해주고 큐에 해당 좌표를 넣어준다.

이렇게 하면 계속해서 최소비용을 갱식할 수 있다. 이미 최소비용이면 어차피 큐에 안넣어주므로 이미 지나온 경로를 체크해 줄 필요도 없다.

---

전체 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <cstring>
using namespace std;
int arr[101][101];
int dp[101][101];
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
int num = 1;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            string s;
            cin >> s;
            for (int j = 0; j < n; j++)
            {
                arr[i][j] = s[j] - '0';
                dp[i][j] = 99999;
            }
        }
        queue<pair<int, int>> q;
        q.push({0, 0});
        dp[0][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 xx = x + dx[i];
                int yy = y + dy[i];
                if (xx < 0 || yy < 0 || xx >= n || yy >= n)
                    continue;
                if (dp[xx][yy] > dp[x][y] + arr[xx][yy])
                {
                    dp[xx][yy] = dp[x][y] + arr[xx][yy];
                    q.push({xx, yy});
                }
            }
        }
        

        cout << '#' << num << ' ' << dp[n - 1][n - 1] << '\n';
        num++;
    }
    return 0;
}