백준
백준2644 - 촌수계산
개발하는꼬마
2019. 8. 20. 15:16
https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. 각 사람의 부모는 최대
www.acmicpc.net
처음에 트리로 접근하였다가 부모-자식관계에서 자식이 부모의 방향으로 탐색하기 위해 다른 방법을 선택하였다. 내가 선택한 방법은 플로이드 와샬이였다. 모든 부모-자식의 비용을 1로 설정한 뒤 플로이드 와샬을 수행하면 최종적으로 도달할 수 있는 곳은 INF로 설정한 값이 아닌 1이 더해진 값이 나오게 된다. 코드에서 플로이드 와샬을 수행한 결과는 최종 촌수이다.
#include <iostream>
#define INF 1000000
using namespace std;
int mat[101][101]; //촌수의 관계를 입력할 공간
int d[101][101]; //플로이드 와샬 결과(촌수)
int num, n, m, CT; //num은 사람 수, n과 m은 관계를 알고 싶은 사람의 번호, CT는 테스트 케이스
//플로이드 와샬을 수행할 함수, k를 거쳐가는 것이 현재의 방법보다 빠르면 갱신
void floydwashall() {
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= num; j++) {
d[i][j] = mat[i][j];
}
}
for (int k = 1; k <= num; k++) {
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= num; j++) {
if (d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
}
int main() {
cin >> num;
cin >> n >> m;
cin >> CT;
fill(&mat[0][0], &mat[num][num], INF); //모든 공간을 무한대로 초기화
//나 자신은 0으로 초기화
for (int i = 1; i <= num; i++) {
mat[i][i] = 0;
}
//모든 비용은 1, 서로 이동이 가능하므로 mat[a][b]와 mat[b][a]의 값을 1로 설정
for (int i = 0; i < CT; i++) {
int a, b;
cin >> a >> b;
mat[a][b] = 1;
mat[b][a] = 1;
}
floydwashall();
//촌수가 정해지지 않으면 -1출력, 촌수가 정해지면 촌수를 출력
if (d[n][m] == INF) {
cout << -1;
}
else {
cout << d[n][m];
}
}