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

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

 

 

 

DFS는 시간 초과 발생. 그렇다고 그리디로 하기에는 변수가 너무 많음 당장 최적을 따라 간다 해도 순간 최악 이지만 후반에 계속 최적이라 더 값이 작게 나오는 경우도 있으므로...

BFS로 풀기에는 BFS는 모든 점을 탐색하지만 visit를 처리해주면 모든 경로 탐색은 불가능.

따라서 visit처리 없이 해야 하는데 이는 무한 반복 야기 

최단 거리를 찾아주기 위해서 BFS와 DP를 어떻게 합칠 수 있을 까

0,0에서 출발이라면 y,x에 도달할 때 까지의 값을 cost라는 배열에 모두 저장하는 것이다.

무한 값으로 초기화 후에 BFS visit처리 없는 방문으로 어떤 경로로도 다 접근 가능하도록 한 뒤에 최소 값에서 갱신 후에 queue에 넣어주는 것이다.

이렇게 하면 같은 값혹은 더 큰값은 queue에 들어오지 않으므로 visit없이도 중복및 반복 방지 가능하다. 

 

#include<iostream>
#include<string.h>
#include<queue>

using namespace std;



string map[100];
int arr[100][100];
int cost[100][100];
int N;

struct Node{
	int y;
	int x;
	int cur;
};

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N;
		memset(cost, 0, sizeof(cost));
		for (int i = 0; i < N; i++)
		{
			cin >> map[i];
		}
		
		for (int i = 0; i < N; i++)
		{
			for(int j = 0; j < N; j++)
			{
				arr[i][j] =  map[i][j] - '0';
				cost[i][j] = 987654321;
			}
		}
		
		cost[0][0] = 0;
		queue<pair<int,int> > que;
		que.push({0,0});
		
		while(!que.empty())
		{
			int y = que.front().first;
			int x = que.front().second;
			
			que.pop();
			
			if(x+1 < N)
			{
				if(cost[y][x+1] > cost[y][x] + arr[y][x+1])
				{
					cost[y][x+1] = cost[y][x] + arr[y][x+1];
					que.push({y,x+1});
				}
			}
			
			if(x-1 >= 0)
			{
				if(cost[y][x-1] > cost[y][x] + arr[y][x-1])
				{
					cost[y][x-1] = cost[y][x] + arr[y][x-1];
					que.push({y,x-1});
				}
				
			}
			
			if(y+1 < N)
			{
				if(cost[y+1][x] > cost[y][x] + arr[y+1][x])
				{
					cost[y+1][x] = cost[y][x] + arr[y+1][x];
					que.push({y+1,x});
				}
			
			}
			
			if(y-1 >= 0)
			{
				if(cost[y-1][x] > cost[y][x] + arr[y-1][x])
				{
					cost[y-1][x] = cost[y][x] + arr[y-1][x];
					que.push({y-1,x});
				}
				
			}
		}
		

		cout << "#" << test_case << " " << cost[N-1][N-1] << endl;

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}