
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' 카테고리의 다른 글
백준 5014_스타트링크(C++) (0) | 2020.10.27 |
---|---|
백준 7569_토마토(C++) (0) | 2020.10.27 |
백준 2667_단지번호붙이기(C++) (0) | 2020.10.26 |
백준 2606_바이러스(C++) (0) | 2020.10.26 |
백준 2178_미로 탐색(C++) (0) | 2020.10.25 |