[백준] 쉬운 최단거리(14940)

 

이 문제는 목표지점에서 모든 지점의 최단거리를 BFS를 통해 찾아주면 되는 문제이다.

 

입력으로 2를 받으면 그 좌표를 기준으로 너비우선탐색을 진행해 준다.

 

문제해결방법

1. arr와 visited배열을 선언해 준다.

2. queue를 선언하고 입력으로 2를 받은 지점을 큐에 넣어준다.(큐에는 x, y, distance와 같은 정보가 필요하다)

3. 큐가 빌 때까지 탐색을 진행한다.

4. 출력은 arr의 내부 값을 출력하면 된다.(단 visited가 0이고 arr가 1이라면 이곳은 탐색이 불가능한 곳으로 간주해서 -1을 출력한다. 왜?? 방문을 하지 못했기 때문)

 

#include <iostream>
#include <queue>

using namespace std;

int arr[1001][1001];
int visited[1001][1001];

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

struct data1
{
	int x;
	int y;
	int distance;
};

queue<data1> Q;

int main(void)
{
	int n = 0;
	int m = 0;

	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)
			{
				data1 temp = { i,j,0 };
				Q.push(temp);
				arr[i][j] = 0;
			}
		}
	}

	while (!Q.empty())
	{
		data1 temp = Q.front();
		Q.pop();

		for (int i = 0; i < 4; i++)
		{
			if (temp.x + dx[i] >= 0 && temp.y + dy[i] >= 0 && temp.x + dx[i] < n && temp.y + dy[i] < m && visited[temp.x + dx[i]][temp.y + dy[i]] == 0 && arr[temp.x + dx[i]][temp.y + dy[i]] == 1)
			{
				arr[temp.x + dx[i]][temp.y + dy[i]] = temp.distance + 1;
				visited[temp.x + dx[i]][temp.y + dy[i]] = 1;
				data1 temp2 = { temp.x + dx[i],temp.y + dy[i],temp.distance + 1 };
				Q.push(temp2);
			}

		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (arr[i][j] == 1)
			{
				if (visited[i][j] == 0)
				{
					cout << -1 << " ";
				}
				else
				{
					cout << 1 << " ";
				}
			}
			else
			{
				cout << arr[i][j] << " ";
			}

		}
		cout << endl;
	}



	return 0;
}