백준 5558 c++

BFS를 활용한 간단한 문제이다. 하나의 테스트 케이스에 대해 방문여부를 초기화하며 순회해야 한다.
크게 어려운 문제는 아니었지만 오랜만에 BFS를 사용해서 각 함수의 수행 여부를 확인할 수 있도록 출력문을 추가했다.

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

using namespace std;

void input_data(vector<vector<char>> &map, pair<int, int> &start, int *N)
{
	//cout << "input_data\n";
	int H, W;
	int i, j;
	char temp;

	cin >> H >> W >> *N;
	map.resize(H, vector<char>(W));
	for (i = 0; i < H; i++)
	{
		for (j = 0; j < W; j++)
		{
			cin >> temp;
			if (temp == 'S')
			{
				start.first = j;
				start.second = i;
			}
			map[i][j] = temp;
		}
	}

	//for (i = 0; i < H; i++)
	//{
	//	for (j = 0; j < W; j++)
	//	{
	//		cout << map[i][j] << " ";
	//	}
	//	cout << "\n";
	//}

	return;
}

void BFS(vector<vector<char>> &map, vector<vector<bool>> &visited, int *start_x, int *start_y, int H, int W, int *count, char destination)
{
	//cout << "BFS " << destination << "\n";
	int current_x, current_y, next_x, next_y;
	vector<pair<int, int>> direction = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
	queue <pair<int, int>> q;
	int i, j, q_size, d_size = direction.size();
	int temp_count = 0;

	q.push({ *start_x, *start_y });
	visited[*start_y][*start_x] = true;
	while (!q.empty())
	{
		q_size = q.size();
		for (j = 0; j < q_size; j++)
		{
			current_x = q.front().first;
			current_y = q.front().second;
			q.pop();
			for (i = 0; i < d_size; i++)
			{
				next_x = current_x + direction[i].first;
				next_y = current_y + direction[i].second;
				if ((next_x >= 0 && next_x < W) && (next_y >= 0 && next_y < H) && visited[next_y][next_x] == false && map[next_y][next_x] != 'X')
				{
					if (map[next_y][next_x] == destination)
					{
						*count += (temp_count + 1);
						*start_x = next_x;
						*start_y = next_y;
						//cout << *count << "\n";
						return;
					}
					else
					{
						q.push({ next_x, next_y });
						visited[next_y][next_x] = true;
					}
				}
			}
		}
		temp_count++;
	}

	return;
}

void find_answer(vector<vector<char>> &map, pair<int, int>& start, int N)
{
	//cout << "find_answer\n";
	int current_start_x = start.first, current_start_y = start.second;
	int i;
	int H = map.size(), W = map.front().size();
	char destination;
	int count = 0;

	for (i = 1; i <= N; i++)
	{
		vector<vector<bool>> visited(H, vector<bool>(W, false));
		//cout << "visited 초기화\n";
		//cout << "start_x : " << current_start_x << " / start_y : " << current_start_y << "\n";

		destination = i + '0';
		BFS(map, visited, &current_start_x, &current_start_y, H, W, &count, destination);
	}
	cout << count << "\n";

	return;
}

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

	vector<vector<char>> cheese_map;
	pair<int, int> start;
	int N;

	input_data(cheese_map, start, &N);
	find_answer(cheese_map, start, N);

	return 0;
}