백준 BOJ 14940 - 쉬운 최단거리

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

14940번: 쉬운 최단거리

간단한 그래프 탐색 문제.

BFS 알고리즘의 구현에 대해서 묻고 있다.

클래스3 문제에 해당한다.

 

굳이 신경써줄 점이라면

입력으로 받은 지도를 잘 저장하고 있다가

숫자를 출력할때

• 원래 갈수 있는 땅인데 고립/격리되어있어서 가지 못한 땅인지
• 원래부터 갈수 없는 땅인지

둘을 구분할때 사용해야 한다.

 

이런 2차원 격자를 탐색할때

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

dx[] 와 dy[]를 만들어놓고

int nx = x+dx[i];
int ny = y+dy[i];

이렇게 순회하면 보다 깔끔한 소스코드를 작성할 수 있다.

이는 4개 방향이 아닌 8개 방향이나 체스 나이트 말의 탐색

등에도 유용하게 활용할 수 있다.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

int ans[1234][1234] = {0};
int in[1234][1234] = {0};

int N,M;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

void bfs(int a, int b){
	memset(ans, -1, sizeof(ans));
	queue<pair<int,int>> q;
	q.push({a,b});
	ans[a][b] = 0;
	
	while(!q.empty()){
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		
		for(int i=0; i<4; i++){
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx==0 || nx==N+1 || ny==0 || ny==M+1) continue;
			
			if(ans[nx][ny] == -1 && in[nx][ny]){
				ans[nx][ny] = ans[x][y]+1;
				q.push({nx,ny});	
			}
		}
	}
	return;
}

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int a,b;
	cin >> N >> M;
	
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			cin >> in[i][j];
			if(in[i][j] == 2){
				a = i;
				b = j;
			}
		}
	}
	
	bfs(a,b);
	
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			if(in[i][j]==0 && ans[i][j]==-1) cout << "0 ";
			if(in[i][j]!=0 && ans[i][j]==-1) cout << "-1 ";
			if(ans[i][j]!=-1) cout << ans[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}