[백준 14940] 쉬운 최단거리

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

---

해설

2인 지점이 도착 지점이라고 했으니 2인 지점을 초기 좌표로 설정해놓고 각 지점까지의 최단 거리를 구하면 되는 문제이다.

따라서 각 지점으로부터 우리가 알고 있는 BFS를 돌려주면 끝이다.

 

문제에서 원래 땅인 부분 중에서 도달할 수 없는 위치는 -1로 출력하라고 하니 이 부분만 조심해주면 될 거 같다.

 

 

˙˙˙

 

소스코드

 

#include <iostream>
#include <queue>
using namespace std;
int xr, yr,cnt;
int di[4] = { -1, 0, 1, 0 };
int dj[4] = { 0, 1, 0, -1 };
int arr[1001][1001];
int res[1001][1001];
bool visited[1001][1001];
int main(){
	int n, m; cin >> n >> m;
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++){
			cin >> arr[i][j];
			if(arr[i][j] == 2)
				xr = j, yr = i;
			if(arr[i][j] == 1)
				cnt++;
		}
	using p = pair<int, pair<int, int > >;
	queue<p> q;
	q.push({0,{xr, yr}});
	visited[yr][xr] = true;
	while(!q.empty()){
		p f = q.front();
		if(f.first == cnt)
			break;
		q.pop();
		for(int i=0; i<4; i++){
			int xx = f.second.first + dj[i];
			int yy = f.second.second + di[i];
			if(xx>=0 && yy>=0 && xx < m && yy < n)
				if(!visited[yy][xx] && arr[yy][xx] == 1){
					res[yy][xx] = f.first+1;
					q.push({f.first+1,{xx, yy}});
					visited[yy][xx] = true;
				} 
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(arr[i][j] == 1 && res[i][j] == 0) cout << "-1" << ' ';
			else cout << res[i][j] << ' ';
		}
		cout << '\n';
	}
}