[백준/BOJ] 백준 1261번 : 알고스팟

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

(i, j)로 갈 수 있는 정점들을 (i, j)가 빈방일 때 0, 벽일 때 1로 (i, j)와 연결하는 그래프를 만들어 다익스트라 알고리즘을 이용하여 (0,0)에서 각각의 정점으로 가는 최단 거리를 구한 뒤, 그중 (n-1, m-1) 정점으로 가는 최단거리를 구한다.

 

코드

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

int n, m;

vector<pair<int, pair<int,int>>> adj[100][100]; //가중치, 정점(위치) 순서로 저장

//start위치부터 stop위치까지 가는데 몇개의 벽을 부수어야 하는지는
//start정점부터 stop정점까지 가는데 최단거리를 구하는 방법으로 풀 수 있다
//간선의 가중치는 빈방일때 0, 벽일때 1 로 하기 때문이다 
int Solve(pair<int,int> start, pair<int,int> stop)
{
	//start정점으로 부터 모든 정점으로 가는데 최단 거리를 저장한다
	//처음에 매우 큰 수로 초기화 한다
	vector<vector<int>> result(n, vector<int>(m, 987654321));

	//-(계산한 거리),정점(위치) 순서로 저장한다
	//-(계산한 거리)로 한 이유는 계산한 거리가 짧은것부터 꺼내기 위해서
	priority_queue<pair<int, pair<int,int>>> pq;

	//시작위치까지 최단거리는 0
	result[start.first][start.second] = 0;
	pq.push(make_pair(-0, start));

	while (!pq.empty())
	{
		pair<int,int> here = pq.top().second;
		int here_cost = -pq.top().first;
		pq.pop();

		//이미 here정점까지 가는 더 짧은 거리를 구했을 때
		if (result[here.first][here.second] < here_cost)
			continue;

		//인접한 정점들을 확인한다
		for (int i = 0; i < adj[here.first][here.second].size(); i++)
		{
			pair<int,int> there = adj[here.first][here.second][i].second;
			int there_cost = adj[here.first][here.second][i].first + here_cost;

			//이전에 계산한 there정점까지의 거리보다 더 짧은 거리를 발견했을때
			if (result[there.first][there.second] > there_cost)
			{
				//업데이트 한다
				result[there.first][there.second] = there_cost;

				//우선순위 큐에 저장한다
				pq.push(make_pair(-there_cost, there));
			}
		}

	}

	//stop위치까지 최단 경로를 구한다
	//즉 간선의 가중치가 빈방일때 0, 벽일때 1이 되므로 이 최단 경로가 stop위치까지 가는데 부수어야 하는 최소 벽의 개수이다
	return result[stop.first][stop.second];
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	string temp;

	cin >> m >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		for (int j = 0; j < m; j++)
		{
			//(i,j)로 갈 수 있는 정점들을 temp[j] - '0'를 가중치로 i,j와 연결한다
			if (i - 1 >= 0)
			{
				adj[i - 1][j].push_back(make_pair(temp[j] - '0', make_pair(i, j)));
			}
			if (j - 1 >= 0)
			{
				adj[i][j - 1].push_back(make_pair(temp[j] - '0', make_pair(i, j)));
			}
			if (i + 1 < n)
			{
				adj[i + 1][j].push_back(make_pair(temp[j] - '0', make_pair(i, j)));
			}
			if (j + 1 < m)
			{
				adj[i][j + 1].push_back(make_pair(temp[j] - '0', make_pair(i, j)));
			}
		}
	}
	
	//(0,0)에서 (n-1,m-1)로 갈때 최소로 부수는 벽의 개수를 구한다
	pair<int, int> start = make_pair(0, 0);
	pair<int, int> stop = make_pair(n - 1, m - 1);

	cout << Solve(start, stop);

	return 0;
}