[BOJ] 2644_촌수계산 with cpp

# 생각

1부터 100까지 연속된 번호에서

주어진 입력의 관계가 주어지기 때문에

정점과 간선이 주어지고 1차원 bfs 탐색을 돌리면 되는 문제이다

 

단, 거리를 구해야 하는 문제이므로

vis배열이 아닌 dist배열을 통해 -1로 초기화를 해주고

촌수를 계산해야하는 시작점 a부터 연결된부분으로 탐색될수록 +1증가를 해주게 되면

b에서의 dist값을 구할 수 있다

탐색이 다 끝난 후 dist값이 -1이면 b지점으로 도달을 하지 못한 것이다

 

 

# 전체 코드

#include <bits/stdc++.h>
using namespace std;

int graph[111][111], dist[111];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;	// 전체 사람 수
	cin >> n;
	int a, b;	// 촌수를 계산해야하는 서로 다른 두 사람의 번호
	cin >> a >> b;
	int m;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		graph[x][y] = 1;
		graph[y][x] = 1;
	}
	fill(dist, dist + n + 1, -1);
	queue<int> q;
	q.push(a);
	dist[a] = 0;	// 시작점
	while (!q.empty())
	{
		auto cur = q.front(); q.pop();
		for (int nxt = 1; nxt <= n; nxt++)
		{
			if (dist[nxt] != -1 or graph[cur][nxt] == 0) continue;
			dist[nxt] = dist[cur] + 1;
			q.push(nxt);
		}
	}
	cout << dist[b];	// 도달했을때의 상태
}

 

---

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

2644번: 촌수계산