백준(BOJ) 알고스팟

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

1261번: 알고스팟

풀이 :

우선 행 열이 아니고 열 행으로 주어지는 n, m에 주의하자.

 

0,0부터 시작해서 n-1 m-1로 가는 것은 priority queue를 통해서 가장 적게 벽을 부순 좌표가 먼저

 

나올 수 있도록 해주었다.

 

마이너스를 붙여서 따로 greater 처리를 하지 않고 오름차순 처리를 해주었다.

 

 

코드 ( C++ )

 

	#include <vector>
	#include <algorithm>
	#include <iostream>
	#include <queue>
	#include <cstring>
	#pragma warning(disable:4996)
	using namespace std;
	const int dy[4] = { 1,-1,0,0 };
	const int dx[4] = { 0,0,1,-1 };
	int a[101][101];
	int n, m;
	int visited[101][101];
	int bfs(int fy, int fx)
	{
	priority_queue<pair<int, pair<int, int>>> pq;
	pq.push({ 0,{0,0} });
	visited[fy][fx] = 1;
	while (!pq.empty())
	{
	int y = pq.top().second.first;
	int x = pq.top().second.second;
	int cnt = -pq.top().first;
	if (y == n - 1 && x == m - 1) {
	return cnt;
	}
	pq.pop();
	for (int k = 0; k < 4; ++k) {
	int ny = y + dy[k];
	int nx = x + dx[k];
	if (!(0 <= ny && ny < n && 0 <= nx && nx < m)) continue;
	if (visited[ny][nx]) continue;
	visited[ny][nx] = 1;
	if (a[ny][nx] == 1)
	pq.push({ -(cnt + 1),{ny,nx} });
	else
	pq.push({ -cnt,{ny,nx} });
	}
	}
	}
	int main()
	{
	cin >> m >> n;
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < m; ++j)
	scanf("%1d", &a[i][j]);
	cout << bfs(0, 0) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub