2644 촌수계산(c++)

촌수 계산

완전 탐색 문제

가계도가 주어지고, 두 사람을 찍었을 때

두 사람간의 촌수를 계산하는 문제

BFS, DFS 까먹을까봐 복습하는 의미로 풀어봤다

1. 문제

---

간단 설명

n명이 주어지고, 두사람 x, y의 번호가 주어진다

m개의 부모자식 관계가 주어지면, x, y가 몇촌인지 확인하는 문제

2. 문제 분석

---

필요변수

• 가문 구성원의 인원수 int n (1 ≤ n ≤ 100)

• 촌수를 계산해야할 두 사람의 번호 int x, y

• 부모자식간의 관계 수 int m

• 가계도 저장용 int family_tree[101][101] : 부모자식 관계라면 1로 표시함. 양방향 그래프

• 한번 방문한 노드를 표시하기 위한 int visited[101]

• BFS
  • 번호와 렙레을 저장하는 구조체 node
  • BFS 탐색을 위한 queue<node> qu
• DFS
  • 정답 기록용 int result
  • 정답을 찾았다면 더이상 탐색을 하지 않기 위한 가지치기용 플래그 bool flag

주의점

• 노드는 1번부터 100번까지. 0번부터 99번이 아님

알고리즘

BFS

1. n, x, y, m 입력받기
2. 연결 정보를 양방향 그래프로 입력받는다
3. BFS탐색 시작
    3-1. 시작노드 x를 레벨 0으로 표시 후 큐에 넣고 방문처리함
    3-2. 큐가 빌때까지 다음을 반복
        3-2-1. 큐의 맨 앞에서 노드를 하나 꺼냄
        3-2-2. 이 노드의 번호가 y라면, 현재 레벨을 리턴하고 종료
        3-2-3. 아니라면, 이 노드와 연결된 노드를 확인
            - 이미 방문한 노드라면 패스
            - 연결되어있지 않다면 패스
            - 위 조건들을 통과했다면, 부모자식 관계이므로, 방문 표시하고 큐에 해당 노드를 레벨+1 해서 넣는다
    3-3. BFS 탐색을 모두 돌았는데도 종료되지 않았다면 -1을 리턴  
4. BFS의 결과값을 출력

DFS

1. n, x, y, m 입력받기
2. 연결 정보를 양방향 그래프로 입력받는다
3. 시작 레벨 0과, 시작노드 x를 매개변수로 가지는 DFS 호출
    3-1. 가지치기 조건 1. 정답을 찾았다면 더이상 찾지 않고 리턴한다
    3-2. 가지치기 조건 2. 레벨이 n을 넘었다면, 즉 모든 노드를 다 돌아봤다면 리턴
    3-3. 가지치기 조건 3. 현재 노드가 찾고있던 y 노드라면, 현재 레벨을 result에 넣고 정답을 찾았다고 표시
    3-4. 위 조건들을 통과했다면
        - 이미 방문한 노드라면 패스
        - 연결되어있지 않다면 패스
        - 위 조건들을 통과했다면, 부모자식 관계이므로, 방문 표시하고 해당 노드와, 레벨+1 해서 DFS를 재귀호출
4. 결과값 result를 출력한다

3. 소스코드

---

BFS

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

using namespace std;

int n, x, y, m;
int family_tree[101][101];
int visited[101];

struct node {
	int num;
	int level;
};

int BFS(int x, int y) {
	queue<node> qu;
	qu.push({ x, 0 });
	visited[x] = 1;

	while (!qu.empty()) {
		node now = qu.front();
		qu.pop();

		if (now.num == y) {
			return now.level;
		}

		// 번호는 1번부터 N번까지있음
		for (int i = 1; i <= n; i++) {			
			if (visited[i] == 1) continue;
			if (family_tree[now.num][i] == 0) continue;
			visited[now.num] = 1;
			qu.push({i,now.level + 1});
		}
	}

	return -1;
}


int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> n;
	cin >> x >> y;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int a, b; 
		cin >> a >> b;
		family_tree[a][b] = 1;
		family_tree[b][a] = 1;
	}

	cout << BFS(x, y) ;

	return 0;
}

DFS

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

using namespace std;

int n, x, y, m;
int family_tree[101][101];
int visited[101];

bool flag = false;
int result = -1;

void DFS(int level, int node) {
	if (flag == true) return;
	if (level >= n) { // 바닥조건 1. 벗어난 경우
		return;
	}
	if (node == y) {
		result = level;
		flag = true;
		return;
	}
	
	for (int i = 1; i <= n; i++) {
		if (visited[i] == 1) continue; // 이미 방문한경우 패스
		if (family_tree[node][i] == 0) continue; // 연결되지 않은경우 패스

		visited[i] = 1;
		DFS(level + 1, i);
		visited[i] = 0;
	}
}


int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> n;
	cin >> x >> y;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int a, b; 
		cin >> a >> b;
		family_tree[a][b] = 1;
		family_tree[b][a] = 1;
	}

	// 2. DFS
	DFS(0, x);
	cout << result;

	return 0;
}