[99클럽/코딩테스트 챌린지/C++] 촌수 계산 문제 해결 - DFS를 이용한 경로 탐색

오늘은 촌수 계산 문제를 해결하면서 DFS(깊이 우선 탐색)를 이용해 두 사람 간의 촌수를 계산하는 방법을 배웠습니다. 이 문제는 부모-자식 간 관계로 구성된 그래프 구조에서 두 노드 간의 거리를 찾는 문제입니다. DFS를 통해 경로를 탐색하고 촌수를 계산하여 해결할 수 있었습니다.

문제 링크 : 

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

 

내 문제 접근 방법

1, 그래프 구성 : 

• 각 사람의 부모-자식 관계를 양방향 그래프로 나타내기 위해 인접 리스트 형태의 map을 사용했습니다. 주어진 관계에 따라 두 사람의 번호를 서로 연결했습니다.

2, DFS를 이용한 촌수 계산 : 

• DFS를 통해 시작 사람부터 목표 사람까지의 경로를 탐색하며, visited 배열을 사용하여 방문 여부와 촌수를 기록했습니다.
• DFS를 재귀적으로 호출하면서 시작 지점에서 현재 지점까지의 촌수를 누적하여 기록하고, 목표 지점에 도달하면 경로 탐색을 종료하도록 했습니다.

3, 도달 불가능한 경우 처리 : 

• 목표 지점에 도달하지 못할 경우 visited[to]는 그대로 초기값 -1을 유지하므로, 출력 시 -1을 출력하여 두 사람 간의 촌수를 계산할 수 없는 경우를 처리했습니다.

코드 풀이

아래는 문제 해결을 위한 최종 코드입니다:

#include <vector>
#include <iostream>
#include <stack>
#include <algorithm>
#include <string>
using namespace std;

int n, from, to, m;
vector<vector<int>> map;
vector<int> visited;
void dfs(int start, int end) {
	for (int near : map[start]) {
		if (visited[near] != -1) continue;
		visited[near] = visited[start] + 1;
		if (near == end)
			return;
		dfs(near, end);
	}
	return;
}

int main()
{
	std::cin >> n;
	std::cin >> from >> to;
	std::cin >> m;
	map = vector<vector<int>>(n + 1);
	visited = vector<int>(n + 1);
	for (int i = 0; i < m; i++) {
		int a, b;
		std::cin >> a >> b;
		map[a].push_back(b);
		map[b].push_back(a);
	}
	for (int i = 0; i < visited.size(); i++) {
		visited[i] = -1;
	}
	visited[from] = 0;
	dfs(from, to);
	std::cout << visited[to] << std::endl;
	
	return 0;
}

위 코드의 문제 접근 방법

1, 그래프 초기화와 관계 입력

• map을 양방향 인접 리스트로 초기화하여 각 사람의 부모-자식 관계를 입력받아 그래프를 구성합니다.
• visited 배열을 사용해 촌수 정보를 저장하며, 미방문 여부를 -1로 초기화했습니다.

2, DFS를 통한 경로 탐색 및 촌수 계산

• DFS 함수에서 visited[start] + 1을 통해 탐색할 때마다 촌수를 누적하여 기록합니다.
• 목표 지점에 도달하면 촌수 누적을 멈추고 결과를 반환하도록 설정했습니다.

3, 도달 불가한 경우 -1 출력 처리

• 탐색이 끝난 후 visited[to]가 여전히 -1이라면 도달 불가를 의미하므로, 이 경우 -1을 출력하도록 처리했습니다.

배운 점

1, DFS를 활용한 경로 탐색의 효율성

• DFS는 경로를 재귀적으로 탐색하며 목표 지점까지의 거리를 측정할 수 있어, 그래프에서 두 노드 간의 관계를 계산할 때 유용하게 사용할 수 있다는 점을 다시 확인했습니다.

2, 방문 여부와 촌수 누적 방식

• visited 배열을 활용해 방문 여부를 -1로 초기화하고, 방문 시 촌수를 누적하여 기록하는 방식이 효과적이라는 점을 배웠습니다.

3, 양방향 그래프 구성과 도달 불가 예외 처리

• 부모-자식 관계는 양방향 그래프로 구현해 부모와 자식을 오가며 탐색할 수 있도록 해야 했습니다. 또한, 도달 불가능한 경우를 처리하기 위해 초기화 상태를 유지하는 방식이 유용하다는 점을 느꼈습니다.

결론

이번 문제를 통해 DFS를 사용하여 두 노드 간의 거리를 계산하는 방법과 예외 상황을 처리하는 방식을 배웠습니다. 앞으로 그래프 탐색 문제를 해결할 때 DFS의 사용법을 숙지하고 방문 여부 및 도달 불가능한 경우를 어떻게 처리할지 고민하는 것이 중요하다고 느꼈습니다.