[Algorithm][C++] SWEA 1249. [S/W 문제해결 응용] 보급로 문제

SWEA 1249. [S/W 문제해결 응용] 보급로 문제

 

풀이 핵심

1. BFS 문제

 

2. 경로의 시간을 저장하는 check 배열을 모두 9 * 100 * 100 으로 초기화 한다. (9 * 100 * 100이 가장 큰 값)

 

3. 새로운 곳(nr, nc)에 방문 할 때 check[nr][nc] 보다 check[cur.r][cur.c] + map[nr][nc] 가 작을 경우에만 큐에 push 한다. 여기서 cur은 현재 위치 정보가 담긴 struct 이다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
using namespace std;

int T, N;
int map[100][100];
int check[100][100];
struct POS { int r, c; };
const int dr[] = { 0,0,1,-1 };
const int dc[] = { 1,-1,0,0 };

int solve() {
	queue<POS> q;
	check[0][0] = 0;
	q.push({ 0,0 });
	while (!q.empty()) {
		POS cur = q.front();
		q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nr = cur.r + dr[dir];
			int nc = cur.c + dc[dir];
			if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
				continue;
			}
			if (check[nr][nc] > check[cur.r][cur.c] + map[nr][nc]) {
				check[nr][nc] = check[cur.r][cur.c] + map[nr][nc];
				q.push({ nr,nc });
			}
		}
	}
	return check[N - 1][N - 1];
}

int main() {
	// freopen("input.txt", "r", stdin);
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		scanf("%d", &N);
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				scanf("%1d", &map[r][c]);
				check[r][c] = 9 * 100 * 100;
			}
		}
		int ret = solve();
		printf("#%d %d\n", tc, ret);
	}
	return 0;
}