[백준 2644] 촌수 구하기

문제설명

해당 문제는 그래프에서 이동 수를 구하는 문제이다

시작 노드에서 도착 노드까지 도달하는데 이동 수를 구하면된다

먼저 총 가족의 수와 구하고자 하는 노드, 연결관계를 입력받는다

촌수 == 도달 하기위해 거쳐가야 하는 노드의 수

라고 생각하고 풀면된다

알고리즘

1. 필요한 정보(가족 수, 구하고자 하는 관계, 관계 정보)를 입력 받는다

2. 현재 노드에 방문 표시를 한다

3. 현재 노드와 연결된 노드를 조회하여 방문 하지 않은 경우 방문한다. 단 방문시 이동 값을 올려준다

4. 노드가 도착점에 닿았을 때 현재 이동한 수를 저장해둔다 

5. 함수를 빠져나오면 저장해둔 이동 수를 출력시킨다

6. 만약 출발점에서 도착점에서 도달하지 못한 경우 -1을 출력시킨다 

코드- (1) ->DFS

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

#define MAX 101
vector <int> graph[101];
bool visited[MAX];
int answer;
void dfs(int x,int y, int cnt) {
	
	visited[x] = true;//방문 표시
	if (x == y)//촌수 계산 완료
		answer = cnt;//촌수 계산 후 값 저장
	for (int i = 0; i < graph[x].size(); i++)
	{
		int next = graph[x][i];
		if (visited[next] != true) {//방문하지 않은 경우 -> 방문
			dfs(next, y , cnt + 1);//다음 노드 조회
		}
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);

	int n;
	int a, b;
	int m;
	cin >> n;
	cin >> a >> b;
	cin >> m;
	for (int i = 0; i < m; i++)//연결관계 저장 
	{
		int x,y;
		cin >> x>>y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	dfs(a, b, 0);
	if (answer == 0)
		cout << -1;//촌수계산이 불가능한 경우 
	else
		cout << answer;//촌수 계산 가능 
	
}

코드-(2) -> BFS

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

#define MAX 101
vector <int> graph[101];

int visit[MAX];

int bfs(int x,int y) {
	queue <int> q;
	q.push(x);

	while (!q.empty()) {
		int current = q.front();
		q.pop();

		if (current == y)
			return visit[y];

		for (int i = 0; i < graph[current].size(); i++)
		{
			int next = graph[current][i];
			if (visit[next]==0) {
				q.push(next);
				visit[next] = visit[current] + 1;
			}
		}
	}
	return -1;
}

int main() {
	cin.tie(0);
	cout.tie(0);

	int n;
	int a, b;
	int m;
	cin >> n;
	cin >> a >> b;
	cin >> m;
	for (int i = 0; i < m; i++)//연결관계 저장 
	{
		int x,y;
		cin >> x>>y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}

	cout << bfs(a,b);
	
}

고찰

해당 문제는 dfs , bfs 모두 가능하다

 

dfs 알고리즘의 경우 겪었던 오류는,

제대로 실행됨에도 불구하고 결과 값이 이상하게 나왔었는데,

재귀함수를 사용하였기 때문에 출발점이 도착점에 도달했을 때 값을 바로 반환하는 것이 아니라 저장이 필요했다

 

bfs 의 경우 겪었던 오류는, 

알고리즘을 구상해놓고, 결과 값 세는데서 헤멨다

단순 방문 표시를 이동 수 카운트로 바꿔서 문제를 해결할 수 있었다