[백준] 2644 촌수계산 c++

문제

www.acmicpc.net/problem/2644

2644번: 촌수계산

 

문제 풀이

bfs사용

 

내가 푼 풀이...

찾아보니까 너무 복잡하게 생각한 것 같다.

하나의 노드를 확인할 때마다 visit을 확인해주어야 한다고 생각했다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int> > relation(101);
bool visit[101] = { false, };

int bfs(int x, int y) {

	queue<pair<pair<int, int>,bool*> > q;//q:
	q.push({ { x,0 },visit });
	while (!q.empty()) {
		int a = q.front().first.first;
		int count = q.front().first.second;
		visit[a] = true;
		q.pop();
		if (a == y)
			return count;
		for (int i = 0; i < relation[a].size(); i++)
		{
			if (relation[a][i] != a &&!visit[relation[a][i]]) {
				q.push({ { relation[a][i], count + 1 },visit });
			}
		}

	}
	return -1;

}

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

	int n, m;//사람의 수 : n, 관계의 개수 : m
	int x, y, temp_x,temp_y;
	cin >> n >> x >> y;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> temp_x >> temp_y;
		relation[temp_x].push_back(temp_y);
		relation[temp_y].push_back(temp_x);
	}

	cout<<bfs(x, y);


	return  0;
}

 

<더 간단한 코드>

 

pair을 사용하지 않고 노드 사이의 거리를 구하는 방법

 

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

vector<vector<int> > relation(101);
int visit[101] ;

int bfs(int x, int y) {
	queue<int>q;
	q.push(x);
	visit[x] = 0;
	while (!q.empty()) {
		int a = q.front();
		q.pop();
		for (int i = 0; i < relation[a].size() ; i++)
		{
			if (visit[relation[a][i]]==-1)
				q.push(relation[a][i]), visit[relation[a][i]] = visit[a]+ 1;
		}
	}
	return visit[y];
}

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

	int n, m;//사람의 수 : n, 관계의 개수 : m
	int x, y, temp_x,temp_y;
	cin >> n >> x >> y;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> temp_x >> temp_y;
		relation[temp_x].push_back(temp_y);
		relation[temp_y].push_back(temp_x);
	}
	memset(visit, -1, sizeof(visit));
	cout<<bfs(x, y);


	return  0;
}