[백준] 촌수계산

문제출처: https://www.acmicpc.net/problem/2644

풀이

bfs를 이용하여 풀었습니다. a에서 b로 가는데 연결된 간선의 수가 정답이므로, check[]배열로  방문여부를 확인함과 동시에, 방문된 현재 좌표의 check배열값을 갱신하므로써 정답을 구할 수 있습니다. 주의할것은 14행,15행에서 최대 n=100까지 입력받기 때문에 32행에서 무의식적으로 i=0;i<n으로 조건을 작성하면 틀립니다. 범위 조심하셔야됩니다.

코드

#include<iostream>
#include<queue>
using namespace std;
int map[101][101];
int check[101];
int n, a, b, m, x, y, ans;
void bfs(int pos);
int main()
{
	cin >> n >> a >> b >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		map[x][y] = 1;
		map[y][x] = 1;
	}
	bfs(a);
	if (check[b] == 0)
		cout << -1 << endl;
	else
		cout << check[b] << endl;

}
void bfs(int pos)
{
	queue<int>q;
	q.push(pos);
	while (!q.empty())
	{
		int temp = q.front(); q.pop();
		//조심, i=0;i<n했으면 틀림
		for (int i = 1; i <=n; i++)
		{
			if(map[temp][i]&&check[i]==0)
			{
				check[i] = check[temp] + 1;
				q.push(i);
			}
		}
	}
}

결과