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

[문제]

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

SW Expert Academy

[풀이]

dfs를 사용하면 시간 초과가 뜬다.

bfs를 사용하여 (N-1,N-1)에 도달하면 가장 짧은 복구시간을 갱신하여 그 다음 부터 최소 복구시간보다 초과되는 경로는 잘라주며 탐색하였다.

 

#include <iostream>
#include <cstring>//memset
#include <cstdio>
#include <queue>
using namespace std;

struct Pos {
	int x, y;
};

int T, N;
int Map[100][100];
int visited[100][100];
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };
int Min = 987654321;

void bfs() {
	queue<Pos>q;
	q.push({ 0,0 });
	visited[0][0] = 0;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		if (x == N - 1 && y == N - 1)
			Min = visited[N-1][N-1];
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				continue;
			if (visited[nx][ny] == -1 && visited[x][y] + Map[nx][ny] < Min) {
				visited[nx][ny] = visited[x][y] + Map[nx][ny];
				q.push({ nx,ny });
			}
			else if (visited[nx][ny] > visited[x][y] + Map[nx][ny] && visited[x][y] + Map[nx][ny] < Min) {
				visited[nx][ny] = visited[x][y] + Map[nx][ny];
				q.push({ nx,ny });
			}
		}
	}
}

void solution() {
	cin >> T;
	for (int t = 1; t <= T; t++) {
		memset(visited, -1, sizeof(visited));
		Min = 987654321;
		cin >> N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				scanf("%1d",&Map[i][j]);
			}
		}
		bfs();
		cout << '#' << t << ' ' << visited[N-1][N-1] << '\n';
	}
}

int main() {
	solution();
	return 0;
}