[Algorithm] 백준 14940번 : 쉬운 최단거리 (C++)

문제 링크 : https://www.acmicpc.net/problem/14940

14940번: 쉬운 최단거리

---

[문제]

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

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

[입력]

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

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

입력에서 2는 단 한개이다

[출력]

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

도달 할 수 없는 위치는 -1을 출력한다.

[알고리즘 분류]

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

[해설]

해당 문제는 다른 그래프 이론 문제와 다를거 없이 2차원 배열과 너비 우선 탐색(BFS)을 이용해 해결할 수 있는 간단한 문제이다.

문제에서는 갈 수 있지만 도달할 수 없는 위치를 -1로 출력하라고 하였으므로, 결과물인 거리를 나타낼 2차원 배열인 d는 -1로 모든 요소를 초기화한다.

그리고 반복되는 입력 중 2가 입력되면 해당 위치를 시작점으로 queue에 push한다.

본격적인 너비 탐색 로직은 처음 push한 queue의 시작점을 바탕으로, 좌우양옆의 인덱스에는 다음 조건 "n*m 범위이며 이전에 탐색하지 않았고 갈 수 없는 땅 '0' 이 아닌가?" 에 부합하면 해당 위치에는 d에서 현재 위치값에 1을 더한 값을 저장해준다.

이렇게 하면 d배열은 다음의 그림과 같은 모습으로 거리를 측정하게 될 것이다.

범위 밖의 영역은 탐색하지 않으며, 위에서 언급한 조건에 부합한다면 다음 위치에는 현재 위치 값에 +1한 값이 저장된다.

그리고 위의 과정을 거쳐 모든 영역을 탐색한다면 d 배열에는 시작점에서의 거리가 모두 측정된 결과만이 남게될 것이며, 이를 반복문을 통해 출력하면 된다.

[정답 코드]

#include <bits/stdc++.h>
#define S 1002
int n,m,b[S][S],d[S][S],dx[]={0,0,1,-1},dy[]={1,-1,0,0};
std::queue<std::pair<int,int>> q;
int main() {
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
	  for(int j=0;j<m;j++){
      d[i][j]=-1;
      scanf("%d",&b[i][j]);
		  if(b[i][j]==2){
		    q.push({i,j});
		    d[i][j]=0;
		  }
	  }
	}
	while(!q.empty()){
		auto c=q.front();
		q.pop();
		for(int i=0;i<4;i++){
		  int nx=c.first+dx[i],ny=c.second+dy[i];
			if(nx >= 0 && nx < n && ny >= 0 && ny < m && d[nx][ny]==-1 && b[nx][ny]!=0){
        d[nx][ny]=d[c.first][c.second]+1;
			  q.push({nx,ny});   
      }
		}
	}
	for(int i=0;i<n;i++){
	  for(int j=0;j<m;j++){
		  if(b[i][j]==0) printf("0 ");
		  else printf("%d ",d[i][j]);
	  }
	  printf("\n");
	}
}

[결과]