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

입력받는 과정에 있어서 숫자가 붙어서 주어졌기 때문에 scanf를 통해 숫자하나씩 입력받음.
처음에는 DFS를 이용한 완전탐색으로 진행했지만 시간초과 발생
BFS와 DP를 사용하는 방식으로 해야 해결됨.

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;

int N;
int map[100][100];
int min_map[100][100];
int dir[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

int findRoad() {
	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));
	min_map[0][0] = 0;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int new_x = x + dir[i][0];
			int new_y = y + dir[i][1];

			if (new_x < 0 || new_x >= N || new_y < 0 || new_y >= N)
				continue;

			if (min_map[new_x][new_y] > min_map[x][y] + map[new_x][new_y]) {
				min_map[new_x][new_y] = min_map[x][y] + map[new_x][new_y];
				q.push(make_pair(new_x, new_y));
			}
		}
	}

	return min_map[N - 1][N - 1];
}

int main() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				scanf("%1d", &map[i][j]);
			}
		}
		memset(min_map, 999999, sizeof(min_map));

		cout << "#" << t << " " << findRoad() << endl;
	}

	return 0;
}