c++ 14496번 그대, 그머가 되어(백준)

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int a, b, n, m, x, y;
	cin >> a >> b; //출발, 도착
	cin >> n >> m; //개수, 쿼리의 개수
	
	vector<int> vec[n+1]; //간선을 저장할 벡터들
	bool v[n]; //방문을 확인할 배열
	memset(v, false, n * sizeof(bool)); //방문을 확인할 배열을 0으로 초기화 합니다.
	
	while(m--) { //간선을 벡터에 저장합니다.
		cin >> x >> y;
		vec[x].emplace_back(y);
		vec[y].emplace_back(x);
	}
	
	if(a == b) { //출발과 도착이 같은 경우, 출력 후 프로그램 종료
		cout << 0;
		return 0;
	}
	
	queue<pair<int, int>> q;
	q.push({a, 0});
	v[a] = true;
	
	while(!q.empty()) { //BFS
		int tmp = q.front().first;
		int value = q.front().second;
		q.pop();
		
		for(int i : vec[tmp]) {
			if(i == b) { //도착지와 같다면 출력 후 프로그램 종료
				cout << value+1;
				return 0;
			}
			
			if(!v[i]) {
				v[i] = true;
				q.push({i, value+1});
			}
		}
	} cout << -1; //찾을 수 없는 경우
}

 

풀이 : BFS

 

1. 간선을 저장하기 위해서 가변배열인 벡터를 이용합니다. a, b 로 입력이 주어지면

vec[a] .emplace_back(b)

vec[b].emplace_back(a)

이렇게 양쪽다 간선이 있음을 저장해야 합니다.

 

2. BFS을 돌립니다.

 

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

14496번: 그대, 그머가 되어