SW Expert Academy - 1249. 보급로

문제링크

• 보급로

문제설명

• N x N 크기의 지도가 주어지고 각 칸은 0~9 숫자로 이루어져 있다.
• 각 칸의 숫자가 의미하는 바는 해당 칸을 복구하는데 드는 시간이다.
• (0,0) 에서 출발하여 (N-1, N-1) 로 가는 방법 중 최소 복구 비용이 드는 경로를 찾아야 한다.
• 이동하는 칸 수는 고려하지 않고 복구 시간만 고려한다.

문제접근

• BFS 를 이용한 완전탐색으로 풀었다. 단, 이동하는 칸 수를 고려하지 않기 때문에 방문한 칸을 재방문해서 새로운 경로를 탐색할 필요가 있다.
  • 방문한 칸을 재방문 하는 경우 이전에 기록한 cost 보다 새롭게 계산된 cost 가 더 작은 경우이다.

구현

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#define INF 100000
using namespace std;

int N;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
vector<string> board;

int bfs() {
	pair<int, int> start = { 0,0 };
	queue<pair<int, int>> q;
	q.push(start);
	vector<vector<int>> dist(N, vector<int>(N, INF));
	dist[0][0] = 0;
	int diff = '0';
	while (!q.empty()) {
		pair<int, int> cpos = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cpos.first + dx[dir];
			int ny = cpos.second + dy[dir];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			int ndist = dist[cpos.first][cpos.second] + (board[nx][ny] - diff);
			if (ndist < dist[nx][ny]) {
				dist[nx][ny] = ndist;
				q.push(make_pair(nx, ny));
			}
		}
	}
	
	return dist[N - 1][N - 1];
}

int main(int argc, char** argv)
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int test_case;
	int T;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N;
		string str;
		board.clear();
		for (int r = 0; r < N; r++) {
			cin >> str;
			board.push_back(str);
		}
		int ans = bfs();
		printf("#%d %d\n", test_case, ans);
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}