백준 2644 c++ "촌수계산" -PlusUltraCode-

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

 

 

 

[필자 사고]

트리형태로 이루어진 촌수를 계산하라는 문제이다.

 

DFS알고리즘과 BFS알고리즘 둘다 사용 가능한 문제이다.

필자는 BFS알고리즘을 선택하였다.

 

선택된 위치부터 모든 경로의 촌수를 저장하는 식으로 문제를 해결했다.

논리상 트리형태이지만 처음 리스트를 생성할때는 

arr[parent].push-back(child);

arr[child].push_back(parent) 와 같이 양방향 리스트로 만들어야 모든 경로를 저장할 수 있다.

 

아래는 소스 코드 해설이다.

 

1. 큐를 사용한 BFS 탐색:
   • BFS 방식은 큐를 이용해 출발 노드(p1)에서 시작하여 목표 노드(p2)까지의 최단 거리를 구하는 알고리즘입니다.
   • myQueue는 탐색할 노드를 저장하는 큐입니다. 출발점 p1을 큐에 넣고 탐색을 시작합니다.
2. 최장 시간이 아닌, 최단 거리로 이동:
   • BFS는 최단 경로를 찾는 데 적합한 탐색 방식입니다. 코드에서는 각 노드를 방문할 때, 그 노드에 도달하기까지의 거리(촌수)를 기록합니다.
   • 현재 노드에서 연결된 다음 노드로 이동할 때, 해당 노드를 아직 방문하지 않았다면 그 노드까지의 거리를 현재 노드까지의 거리에서 1을 더해 계산합니다.
3. 백트래킹 대신 너비 우선 탐색:
   • 백트래킹(backtracking)은 가능한 모든 경로를 탐색하며 답을 찾는 방식이지만, 이 코드에서는 BFS를 사용하여 최단 경로를 효율적으로 찾습니다.
   • visited 배열을 통해 이미 방문한 노드를 다시 방문하지 않도록 하여 무한 루프를 방지합니다.
4. 간선 수를 세는 방식:
   • 코드에서 촌수(거리)를 구하는 핵심 부분은 Distance 배열입니다. 출발 노드에서 각 노드까지의 촌수를 기록하며, 목표 노드(p2)에 도달하면 그 값을 출력합니다.
   • BFS 탐색 중, 목표 노드에 도달하면 그때까지 누적된 촌수(경로의 길이)를 출력합니다. 만약 목표 노드에 도달할 수 없으면 -1을 출력합니다.

코드 흐름

1. 입력 처리 (Input 함수):
   • N: 사람의 수 (노드의 수).
   • p1, p2: 촌수를 계산할 두 사람.
   • M: 관계의 수 (간선의 수).
   • 각 사람 간의 관계를 arr이라는 2차원 벡터에 저장합니다. 이때 관계는 양방향이므로 두 사람 간의 관계를 서로 저장해 줍니다.
2. BFS 탐색 (BFS 함수):
   • 큐를 사용해 출발 노드에서부터 너비 우선으로 탐색을 시작합니다.
   • 출발 노드에서 인접한 모든 노드를 탐색하며, 거리를 갱신하고 큐에 넣습니다.
   • 목표 노드에 도달할 때까지 반복합니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, p1, p2, M;
vector<vector<int>> arr;
vector<bool> visited;
vector<int> Distance;

void Input() {
	cin >> N >> p1 >> p2 >> M;
	visited.resize(N + 1, false);
	Distance.resize(N + 1, -1);

	arr.resize(N + 1);
	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;
		arr[s].push_back(e);
		arr[e].push_back(s);
	}
}

void BFS(int startIdx) {
	queue<int> myQueue;
	myQueue.push(startIdx);
	visited[startIdx] = true;
	Distance[startIdx] = 0;

	while (!myQueue.empty()) {
		int nowIdx = myQueue.front();
		myQueue.pop();

		for (int nextIdx : arr[nowIdx]) {
			if (visited[nextIdx] == true)continue;
			Distance[nextIdx] = Distance[nowIdx] + 1;
			myQueue.push(nextIdx);
			visited[nextIdx] = true;
		}
	}
}


void GameStart() {
	BFS(p1);
	if (Distance[p2] == -1)cout << -1;
	else cout << Distance[p2];
}

int main(void) {
	Input();
	GameStart();
}