글 읽기 - 단순 BFS 문제같은데

busyhuman 6년 전 0

단순히 BFS로 구현했는데

어디가 잘못생각한건가요?

반례라도 알려주시면 감사합니다.

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <deque>
#include <bitset>
using namespace std;

int arr[1001][1001] = { {0} };
int n, m, a, b;
int maxi = -1;

void BFS() {
	deque<int> y, l;
	
    // 출발지에서 나가는 경로 모두 큐에 넣기
	for (int i = 1; i <= n; i++) {
		if (arr[a][i] == 1) {
			y.push_back(i);
			l.push_back(1);
		}
	}

	while (!y.empty()) {
	//	cout << y.front() << " " << l.front() << '\n';
		if (y.front() == b) break;
		
        // 현재 점에서 이어진 경로 모두 찾고, 간선 제거
		for (int i = 1; i <= n; i++) {
			if (arr[y.front()][i]) {
				y.push_back(i);
				l.push_back(l.front() + 1);
				arr[y.front()][i]=arr[i][y.front()] = 0;
			}
		}
		y.pop_front();
		l.pop_front();
	}

	if (l.empty()) cout << "-1";
	else cout << l.front();
}

int main(){
	int x, y;
	cin >> a >> b >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		arr[x][y] = arr[y][x] = 1;
	}
	BFS();
}