삼성 SW Expert Academy 1249번

삼성 SW Expert Academy에 괜찮은 문제들이 많이 있는 것 같아 요즘 몇 문제 풀어보았습니다. 

문제는 삼성 SW Expert Academy 가입 후 확인 가능하여 따로 올릴 수 없습니다.

 

문제 내용은 간단하다. 보급로가 주어져있을 때 어떤 경로로 가장 빨리 갈 수 있는가입니다.

댓글을 보니 dfs로 풀거나 다익스트라로 푸신 분들도 계셨지만, 저는 bfs와 dp를 섞어서 풀었습니다.

주의할 점은 해당 지점을 들렀다하더라도, 다른 경로에서 더 빠른 케이스가 있을 수 있기 때문에 이를 체크해야 합니다.

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<cstdio>
 
using namespace std;
 
int n;
int board[101][101];
int dy[4] = {0,0,1,-1};
int dx[4] = {1,-1,0,0};
bool check[101][101];
int dp[101][101];
 
void make_board(int size)
{
    for(int i=1;i<=size;i++)
    {
        string s;
        cin >> s;
        for(int j=0;j<s.size();j++)
        {
            int num = s[j] - '0';
            board[i][j+1] = num;
            check[i][j+1] = false;
            dp[i][j+1] = board[i][j+1];
        }
         
    }
     
    return;
}
 
void bfs(int size)
{
    int sy = 1;
    int sx = 1;
    int cnt = board[sy][sx];
    queue<pair<int,int>> q;
    q.push({sy,sx});
     
    while(!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
       
        q.pop();
         
        for(int i=0; i<4; i++)
        {
            int ny = y+dy[i];
            int nx = x+dx[i];
             
            if(ny>=1 && ny<=size && nx>=1 && nx<=size)
            {
                if(check[ny][nx]==false || dp[ny][nx] > dp[y][x]+board[ny][nx]){
                    check[ny][nx] = true;
                    dp[ny][nx] = dp[y][x]+board[ny][nx];
                    q.push({ny,nx});
                }
            }
        }
    }
     
    return;
}
 
int main(int argc, char** argv)
{
    int test_case;
    int T;
    
    cin>>T;
    
    for(test_case = 1; test_case <= T; ++test_case)
    {
        cin >> n;
        make_board(n);
         
        bfs(n);
         
        cout << "#" << test_case << ' ' << dp[n][n] << '\n';
 
    }
    return 0;
}