[14940] 쉬운 최단거리

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
int mp[1001][1001], v[1001][1001];
int N, M;
int main() {
	FAST;
	pi s;
	cin >> N >> M;
	rep(i, N)rep(j, M) {
		cin >> mp[i][j];
		v[i][j] = -1;
		if (mp[i][j] == 2)s = { i,j }, v[i][j] = 0;
		if (mp[i][j] == 0)v[i][j] = 0;
	}
	queue<pi>q;
	q.push(s);
	while (!q.empty()) {
		auto [y, x] = q.front();
		q.pop();
		rep(i, 4) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 0 && ny < N && nx >= 0 && nx < M && v[ny][nx]==-1) {
				if (mp[ny][nx] == 1) {
					v[ny][nx] = v[y][x] + 1;
					q.push({ ny,nx });
				}
			}
		}
	}

	rep(i, N) {
		rep(j, M) {
			cout << v[i][j] << " ";
		}
		cout << "\n";
	}
}

 

 BFS를 사용합니다.

visit배열에 원래부터 못 지나가는 칸은 0으로 초기화하고, 지나갈 수 있는 칸은 -1로 초기화 합니다.

출발 지점으로부터 bfs를 수행하면 지나갈 수 있는칸만 최단거리가 저장됩니다.