백준 14940 c++

BFS를 통해 각 위치로부터 목표지점까지의 거리를 구하는 문제이다.
각 위치로부터 목표까지의 거리를 각각 구하는 것보다 목표에서 각 위치까지의 최단거리를 구하는 것이 더 효율적이다.
정답을 넣을 벡터를 전부 -1로 초기화 하고, 그래프 정보를 입력받을때 0의 위치를 미리 저장한다.

#include <iostream>
#include <vector>
#include <queue>
#include <vector>

using namespace std;

int n, m;
vector <vector<int>> graph;
vector <vector<int>> result;
vector <vector<bool>> visited;

void input_graph(int *dest_x, int *dest_y)
{
	int i, j, temp;

	cin >> n >> m;
	graph.resize(n, vector<int>(m, 0));
	visited.resize(n, vector<bool>(m, false));
	result.resize(n, vector<int>(m, -1));

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			cin >> temp;
			if (temp == 2)
			{
				*dest_x = j, *dest_y = i;
			}
			else if (temp == 0)
			{
				result[i][j] = 0;
				//visited[i][j] = true;
			}
			graph[i][j] = temp;
		}
	}

	/*
	cout << "\n";
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			cout << graph[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "dest_x : " << *dest_x << " dest_y : " << *dest_y << "\n";
	*/

	return;
}

void BFS(int start_x, int start_y)
{
	int current_x, current_y, next_x, next_y;
	int i, j;
	int count = 0, q_size, direction_size;
	vector<pair<int, int>> direction = { {1, 0},{0, 1},{-1, 0},{0, -1} };
	queue<pair<int, int>> q;

	q.push({ start_x, start_y });
	visited[start_y][start_x] = true;
	result[start_y][start_x] = count;
	count++;
	direction_size = direction.size();
	while (!q.empty())
	{
		q_size = q.size();
		for (i = 0; i < q_size; i++)
		{
			current_x = q.front().first;
			current_y = q.front().second;
			q.pop();
			for (j = 0; j < direction_size; j++)
			{
				next_x = current_x + direction[j].first;
				next_y = current_y + direction[j].second;
				if ((next_x >= 0 && next_x < m) && (next_y >= 0 && next_y < n) && visited[next_y][next_x] == false)
				{
					if (graph[next_y][next_x] != 0)
					{
						visited[next_y][next_x] = true;
						q.push({ next_x, next_y });
						result[next_y][next_x] = count;
					}
				}
			}
		}
		count++;
	}

	return;
}

void find_result(int* dest_x, int* dest_y)
{
	int start_x = *dest_x, start_y = *dest_y;
	int i, j;

	BFS(start_x, start_y);
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			cout << result[i][j] << " ";
		}
		cout << "\n";
	}

	return;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int dest_x, dest_y;

	input_graph(&dest_x, &dest_y);
	find_result(&dest_x, &dest_y);

	return 0;
}