[C++] SWEA 1249번: 보급로

🔗 문제

SW Expert Academy

SW Expert Academy

 

🖍 풀이

DFS는 시간초과고 BFS이라고 생각해서 풀면 오답이다. (경험담)

 

왜냐하면 생각해보면 map의 좌표 (x, y)까지 오는 경로는 다양하다.

가는 길이 0, 1로만 이루어진 것이 아니기 때문에 첫 방문이 최소 경로라고 단정지을 수 없다.

 

그래서 상하좌우로 이동하면서 (x, y)까지 걸린 시간을 계속해서 갱신해주어야 한다.

visited[x][y]로 재방문를 판단하기는 하지만 그냥 갱신인지 신규인지만 판단하는 용도로 사용해줬다.

• 다익스트라의 개념을 알고 있으면 내 풀이를 이해하는데 도움됨

 

💾  소스

#include <iostream>
#include <memory.h>
#include <queue>

const int MAX = 100+2;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

int map[MAX][MAX] = {0, };
int N, answer = 1e9;

typedef  std::pair<int, int> pii;

bool isValid(const int x, const int y)
{
    if(x<0 || y<0 || x>=N || y>=N)
        return false;
    
    return true;
}

void solve()
{
    std::queue<pii> q;
    q.push({0, 0});
    
    
    bool visited[MAX][MAX] = {false, };
    visited[0][0] = true;
    
    
    int dp[MAX][MAX] = {0, };
    dp[0][0] = 0;
    
    
    while(!q.empty())
    {
        int nowX = q.front().first;
        int nowY = q.front().second;

        if(nowX == N-1 && nowY == N-1)
        {
            answer = std::min(answer, dp[N-1][N-1]);
        }
        q.pop();
        
        if(answer <= dp[nowX][nowY])
            continue;
        
        for(int d=0; d<4; ++d)
        {
            int x = nowX + dx[d];
            int y = nowY + dy[d];
            
            if(isValid(x, y) == false)
                continue;
            
            **// 더 낮은 가중치 발견하면 갱신하기
            if(visited[x][y])
            {
                if(dp[x][y] > dp[nowX][nowY] + map[x][y])
                {
                    q.push({x, y});
                    dp[x][y] = dp[nowX][nowY] + map[x][y];
                }
            }
            else
            {
                dp[x][y] = dp[nowX][nowY] + map[x][y];
                q.push({x, y});
                visited[x][y] = true;
            }**

        }
    }
}

int main()
{
    int T; char c;
    std::cin >> T;
    
    for(int tc=1; tc<=T; ++tc)
    {
        std::cin >> N;
        for(int i=0; i<N; ++i)
        {
            for(int j=0; j<N; ++j)
            {
                std::cin >> c;
                map[i][j] = c-'0';
            }
        }
        
        answer = 1e9;
        solve();
        std::cout << '#' << tc <<' ' << answer << '\\n';
    }
    return 0;
}