문제

boj14496_1 boj14496_2

야민정음이길래 은근히 기대했으나 역시 그냥 BFS를 쓰는 간단한 그래프 문제였다. 문제에서 (a, b)일 때 a->b인지 a<->b인지 명시하지 않았는데 예제를 보고 a<->b라는 것을 알았다. 이번에는 b에 도달하면 BFS를 종료하도록 break문을 넣어줬다. 우리는 b만 알면 되는거니까..!

#include <iostream>
#include <vector>
#include <queue>
#define MAX 1001
using namespace std;

vector<int> graph[MAX];
int dist[MAX];
bool visit[MAX];

void BFS(int src, int dst) {
	queue<int> q;
	dist[src] = 0;

	q.push(src);
	while (!q.empty()) {
		int now = q.front();
		q.pop();

		if (now == dst) break;
		for (auto it = graph[now].begin(); it < graph[now].end(); it++) {
			int next = *it;
			if (!visit[next]) {
				dist[next] = dist[now] + 1;
				visit[next] = true;
				q.push(next);
			}
			visit[now] = true;
		}
	}
}

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

	int a, b, N, M, from, to, i;
	cin >> a >> b; // a를 b로 바꾸는
	cin >> N >> M;

	for (i = 0; i < M; i++) {
		cin >> from >> to;
		graph[from].push_back(to);
		graph[to].push_back(from);
	}

	if (a == b) cout << 0 << endl;
	else {
		BFS(a, b);
		if (!visit[b]) cout << -1 << endl;
		else cout << dist[b] << endl;
	}
	return 0;
}