[SWEA] #1249 _ 보급로

[보급로] https://www.swexpertacademy.com/

SW Expert Academy

 

처음에는 dp로 풀 수 있을 것이라고 생각하였다.

그러나, 아래와 같이 돌아가야하는 경우에 내가 생각한 dp로 풀면 올바른 답을 얻을 수 없다.

 

dp의 결과로는 7이 최소 시간으로 구해지나, 최소 시간은 6이다.

이와 같은 경우를 고려하기 위해 bfs를 사용하였다.

 

지도에서 bfs로 그냥 탐색하면 시간이 너무 오래 걸리기 때문에 불필요한 탐색은 줄여야한다.

dp의 결과를 기준으로 두고,

dp의 값 보다 작은 경우에만 bfs로 탐색하여 최소 시간을 구하는 방식으로 구현하였다.

(다른 사람의 풀이를 보니 bfs를 하면서 시간이 커지면 멈추는 방식으로 한 것 같았다.)

 

입력데이터가 띄어쓰기가 없기 때문에 문자로 한 글자씩 받아

48 (0의 ascii 값 == 48) 을 빼줌으로써 숫자로 변환하였다.

(찾아보니 %1d를 이용하면 1자리만 받아 숫자로 바로 입력 받는 것도 가능하다.)

 

[ 소스 코드 ]

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAX 100
#define INF 999999

using namespace std;
int map[MAX + 1][MAX + 1] = { 0, }, n;
int dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };

int solve();
int main() {
	int test_case;
	char input;

	scanf("%d", &test_case);
	for (int i = 1; i <= test_case; i++) {
		scanf("%d", &n);
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				scanf("%c", &input);
				if (input == '\n') scanf("%c", &input);
				map[j][k] = input - 48;
			}
		}
		printf("#%d %d\n", i, solve());
	}

	return 0;
}

int solve() {
	queue<pair<int, int> > q;
	pair<int, int> idx;
	int path[MAX + 1][MAX + 1];
	int x, y;

	for (int i = 0; i < n; i++) memset(path[i], INF, sizeof(int)*n);

	path[0][0] = 0;
	for (int i = 0; i < n; i++) { //use dp
		for (int j = 0; j < n; j++) {
			if (i == 0 && j == 0) continue;
			else if (i == 0) path[i][j] = path[i][j - 1] + map[i][j];
			else if (j == 0) path[i][j] = path[i - 1][j] + map[i][j];
			else path[i][j] = min(path[i][j - 1] + map[i][j], path[i - 1][j] + map[i][j]);
		}
	}

	for (int i = 0; i < n; i++) { //use bfs
		for (int j = 0; j < n; j++) {
			q.push(make_pair(i, j));
			while (!q.empty()) {
				idx = q.front();
				q.pop();
				for (int k = 0; k < 4; k++) {
					x = idx.second + dx[k];
					y = idx.first + dy[k];
					if (x < 0 || y < 0 || x >= n || y >= n) continue;
					if (path[y][x] > path[idx.first][idx.second] + map[y][x]) {
						q.push(make_pair(y, x));
						path[y][x] = path[idx.first][idx.second] + map[y][x];
					}
				}
			}
		}
	}
	return path[n - 1][n - 1];
}