본문 바로가기

algorithm/BOJ

백준 2644_촌수계산(C++)

 

www.acmicpc.net/problem/2644

 

2644번: 촌수계산

사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진

www.acmicpc.net

[문제 풀이]

DFS를 이용하여 문제를 풀었습니다.

이 문제는 주어진 x, y 사이의 관계를 찾는 문제입니다. 이 문제의 경우 DFS와 BFS 모두 사용이 가능합니다. 저는 DFS를 이용하여 문제를 해결했습니다.

 

코드 설명

  • 2차원 배열 map에 관계를 기록 합니다.
  • map의 x행의 배열에 체크된 i의 자식들을 조사합니다.
  • i가 y 이면 1촌을 반환하고 아닐 경우 i의 자식들을 찾아봅니다.
  • 자식이 y이면 관계를 값에 넣어줍니다.

[코드]

#include<iostream>

using namespace std;

int n, m;
int person1, person2;
int relation = -1;

int visit[101];
int map[101][101];

void DFS(int idx, int cnt) {

	if (idx == person2) {
		relation = cnt;
		return;
	}

	for (int i = 1; i <= n; i++)
		if (visit[i] == 0 && map[idx][i] == 1) {
			visit[i] = 1;
			DFS(i, cnt + 1);
		}

}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	cin >> person1 >> person2;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;

		map[temp1][temp2] = 1;
		map[temp2][temp1] = 1;
	}

	visit[person1] = 1;

	for (int i = 1; i <= n; i++) 
		if (visit[i] == 0 && map[person1][i] == 1) {
			if (i == person2) {
				relation = 1;
				break;
			}
			visit[i] = 1;
			DFS(i, 1);
		}
	

	cout << relation << endl;

	return 0;
}

 

 

'algorithm > BOJ' 카테고리의 다른 글