PS/깊이 우선 탐색, 너비 우선 탐색[DFS, BFS]

백준 2644 촌수계산(c++)

SeungbeomKim 2022. 8. 15. 20:19

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

 

2644번: 촌수계산

사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어

www.acmicpc.net

<코드>

#include <iostream>
#include <queue>
#define max 101
using namespace std;
int a,b;
int board[max][max];
int x,y,n,m;
int visited[max] = {0};
int cnt[max] = {0};
void bfs(int node)
{
	
	queue<int>q;
	q.push(node);
	while(!q.empty()){
		node = q.front();
		q.pop();
		for(int i=1;i<=n;i++)
		{
			
			if(board[node][i] && !visited[i])
			{
				q.push(i);
				visited[i] = true;
				cnt[i] = cnt[node]+1;
			}
		}
	}
}
int main()
{
	cin>>n;
	cin>>x>>y;
	cin>>m;
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;
		board[a][b] = board[b][a] = 1;		
	}
	bfs(x);
	
	if(!cnt[y]){
	cout<<-1;
	return 0;
	}
	cout<<cnt[y];
}

<풀이과정>

bfs로 접근해서 풀었다. start(시작 정점) , end(마지막 정점)을 의미한다. 

큐에 시작 정점을 push하고 시작정점과 연결된 부분을 찾아서 개수를 하나 증가시켜주면 된다.

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

다음 테스트케이스를 보면

7(부모노드) 2 1 3(자식노드) 순서로 촌수가 3임을 확인할 수 있다. 

'PS > 깊이 우선 탐색, 너비 우선 탐색[DFS, BFS]' 카테고리의 다른 글

백준 5567 결혼식(c++)  (0) 2022.08.16
백준 1926 그림(c++)  (0) 2022.08.16
백준 1697 숨바꼭질(c++)  (0) 2022.08.14
백준 7576 토마토(c++)  (0) 2022.08.14
17086 아기 상어 2(c++)  (0) 2022.08.12