백준 2644 [C++]

www.acmicpc.net/problem/2644

2644번: 촌수계산

1. 풀이방법

 

- 촌수를 계산하는 문제입니다 (두 정점 사이에)

 

- dfs를 통해서 계산을 하였고 간선의 가중치 (촌수가 1씩 증가)가 1이므로 bfs로도 쉽게 표현 가능할 것으로 보입니다.

 

- 두 정점이 인접했는지를 확인하는 연산이 주로 쓰이므로 인접행렬방식으로 그래프를 구현하였습니다.

 

 

 

2. 주의사항

 

- 딱히없음, 특별한 조건도 없고..

 

 

3. 나의코드

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

int n, m;
int target1, target2;
bool connected[101][101];
bool visited[101];
bool suc;

void inputs() {
	cin >> n >> target1 >> target2;
	cin >> m;
	int tmp1, tmp2;
	for (int i = 0; i < m; i++) {
		cin >> tmp1 >> tmp2;
		connected[tmp1][tmp2] = true;
		connected[tmp2][tmp1] = true;
	}
}

void findchon(int t,int cnt) {
	visited[t] = true;
	if (t == target2) { cout << cnt << "\n";
	suc = true; return;
	}
	for (int i = 1; i <= n; i++) {
		if (i != t) {
			if (connected[t][i] && !visited[i]) {
				findchon(i, cnt + 1);
			}
			if (suc) break;
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	findchon(target1,0);
	if (suc == false) cout << -1 << "\n";

	return 0;
}