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

[URL]

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

SW Expert Academy

 

 

[풀이 과정]

* BFS

유사문제: 단지번호붙이기, 최단경로

경로중 최소값을 넣어줘야하는 로직 !!

 

1. input & init

 

2. BFS()

 

[소스 코드]

 

#include <stdio.h>
#include <string.h>
#include <queue>
#define MAX 101
 
using namespace std;
 
int map[MAX][MAX];
int N;
 
bool check[MAX][MAX];
int dist[MAX][MAX];
 
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
int BFS() {
    queue <pair <int, int>> q;
 
    check[0][0] = true;
    dist[0][0] = 0;
 
    q.push(make_pair(0, 0));        // 시작점
 
    while (!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
 
        q.pop();
 
        for (int k = 0; k < 4; k++)
        {
            int nx = cx + dx[k];
            int ny = cy + dy[k];
 
            if (nx >= 0 && nx < N && ny >= 0 && ny < N)        // map범위 안인가?
            {                    
                // 방문한 적 없는가? || (최소값 계산!) 기존값 dist[nx][ny] 보다 작은 값 계산되면 넣어준다.
                if (check[nx][ny] == false || dist[nx][ny] > dist[cx][cy] + map[nx][ny])
                {
                    check[nx][ny] = true;
                    dist[nx][ny] = dist[cx][cy] + map[nx][ny];
 
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }        
 
    return dist[N - 1][N - 1];        // 도착점 return
}
 
void init() {
    for (int i = 0; i < MAX; i++)
    {
        memset(map[i], 0, sizeof(int) * MAX);
        memset(check[i], 0, sizeof(bool) * MAX);
        memset(dist[i], 0, sizeof(int) * MAX);
    }
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%1d", &map[i][j]);
        }
    }
}
 
int main() {
 
    int T;
    scanf("%d", &T);
 
    for (int tc = 0; tc < T; tc++)
    {
        init();
 
        printf("#%d %d\n", tc + 1, BFS());
    }
    return 0;
}