기본적인 BFS 문제
bfs만 짜면 AC받을수 있다.
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진
www.acmicpc.net
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
vector<int> v[123];
queue<int> q;
int visit[123] = {0};
void bfs(){
while(!q.empty()){
int node = q.front();
q.pop();
for(int i=0; i<v[node].size(); i++){
if(!visit[v[node][i]]){
q.push(v[node][i]);
visit[v[node][i]] = visit[node] + 1;
}
}
}
}
int main(){
int n,a,b;
int m,x,y;
scanf("%d %d %d", &n, &a, &b);
scanf("%d", &m);
for(int i=0; i<m; i++){
scanf("%d %d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
q.push(a);
visit[a] = 1;
bfs();
printf("%d", visit[b]-1);
return 0;
}워낙 어렵지 않은 문제라
설명은 생략하도록 하겠다.
반응형