-
https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. 각 사람의 부모는 최대
www.acmicpc.net
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include<iostream>#include<queue>using namespace std;int n, a, b;vector<int> map[101];bool d[101]; int dist[101];void bfs(int x) {queue<int> q;q.push(x);d[x] = true;while (!q.empty()) {x = q.front(); q.pop();for (int i = 0; i < map[x].size(); i++) {if (d[map[x][i]] == false){dist[map[x][i]] = dist[x] + 1;d[map[x][i]] = true;q.push(map[x][i]);}}}}int main() {ios_base::sync_with_stdio(0);cin.tie(0);cin >> n >> a >> b;int num;cin >> num;for (int i = 0; i < num; i++) {int x, y;cin >> x >> y;map[x].push_back(y);map[y].push_back(x);}bfs(a);if (dist[b] != 0) {if (a == b) {cout << 0 << '\n';}elsecout << dist[b] << '\n';}else cout << -1 << '\n';return 0;}http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter간단한 BFS문제 하지만 BFS개념의 모든것을 담고있다 특히 인접리스트 관련해서..
BFS하면서 행렬쓰는거에 익숙해져있다보니 인접리스트를 잘못하는편인데 좋은연습이 된것같다
오늘 풀었던 게리멘더링 같은곳에서 충분히 쓸수있는 BFS개념