백준 14496번 그대, 그머가 되어 C++

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

 

bfs탐색을 통해 해결할 수 있는 문제이다. 

문제를 읽어보면 한쪽 방향으로만 그래프가 그려지는 것 같은데 양방향 모두 고려해야 맞는 답이 나온다.

문제에 설명을 보충하면 좋을 것 같다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

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

	int a, b, n, m;
	cin >> a >> b >> n >> m;
	if (a == b) {
		cout << 0;
		return 0;
	}
	vector<vector<int>> v(n + 1, vector<int>());
	for (int i = 0; i < m; i++) {
		int start, end;
		cin >> start >> end;
		v[start].push_back(end);
		v[end].push_back(start);
	}
	int ans = -1;
	queue<pair<int, int>> q;
	q.push({ a,0 });
	vector<vector<bool>> visited(n + 1, vector<bool>(n + 1, false));
	while (!q.empty()) {
		auto curr = q.front();
		q.pop();
		for (auto next : v[curr.first]) {
			if (next == b) {
				ans = curr.second + 1;
				cout << ans;
				return 0;
			}
			if (visited[curr.first][next]) continue;
			q.push({ next,curr.second + 1 });
			visited[curr.first][next] = true;
		}
	}
	cout << ans;
};