문제링크:https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. 각 사람의 부모는 최대
www.acmicpc.net
처음에 보자마자 생각난건 union-find 알고리즘이였다. 서로 친척인지 확인을 해주기 위한 방법으로 사용하였다.
그이후에는 몇가지 케이스를 대입보면서 촌수계산을 분명하게 하기위해서는 완전탐색을 해야하는 것을 깨닭았고,
dfs와 bfs중에 고민하였다. 아마 dfs로도 풀이가 가능할 것이다. 탐색에 좀 더 적합한 bfs를 선택했다.
1. search_root() 함수를 통해서 서로 친척인지 확인
2. 출발점x로부터 y까지 도달하는 과정에서 각 값들을 큐에 저장하며 해당 직계도를 탐색
3. bfs함수 호출이 끝난후 cnt[y]값을 출력 ( 전달받아 오면서 값이 +1씩 증가했으므로 촌수와 동일)
bfs에서 !visited[arr[i][1]] 의 조건은 최소의 촌수를 선택해야하기 때문입니다.
정답코드입니다.
#include <iostream>
using namespace std;
int n = 0, m = 0, x, y,a,b;
int arr[101][2] = { 0 };
int root_x, root_y;
int cnt[101] = { 0 };
bool visited[101] = { 0 };
void bfs() {
int que[101] = { 0 };
int started = 0, ended = 0;
que[ended++] = x;
while (started != ended) {
int val = que[started++];
visited[val] = 1;
for (int i = 0; i < m; i++) {
if (arr[i][0] == val && !visited[arr[i][1]]) {
que[ended++] = arr[i][1];
cnt[arr[i][1]] = cnt[val] + 1;
}
if (arr[i][1] == val && !visited[arr[i][0]]) {
que[ended++] = arr[i][0];
cnt[arr[i][0]] = cnt[val] + 1;
}
}
}
}
void search_root() {
root_x = x;
root_y = y;
while (1) {
bool t = false, r = false;
for (int i = 0; i < m; i++) {
if (arr[i][1] == root_x) {
t = true;
root_x = arr[i][0];
}
if (arr[i][1] == root_y) {
r = true;
root_y = arr[i][0];
}
}
if (t == false && r == false)
break;
}
}
int main() {
cin >> n;
cin >> x >> y;
cin >> m;
for (int i = 0; i < m; i++)
cin >> arr[i][0]>>arr[i][1];
search_root();
if (root_x != root_y) {
cout << -1 << endl;
return 0;
}
bfs();
cout << cnt[y] << endl;
}
움.. 그런데... 생각해보니 searchroot가 필요가 없죠? 어차피 탐색이 안되면 cnt[y]값을 0일 것이기 때문에 그때만 -1로 출력을 해주면 되기 때문입니다.
수정답안 입니다.
#include <iostream>
using namespace std;
int n = 0, m = 0, x, y,a,b;
int arr[101][2] = { 0 };
int root_x, root_y;
int cnt[101] = { 0 };
bool visited[101] = { 0 };
void bfs() {
int que[101] = { 0 };
int started = 0, ended = 0;
que[ended++] = x;
while (started != ended) {
int val = que[started++];
visited[val] = 1;
for (int i = 0; i < m; i++) {
if (arr[i][0] == val && !visited[arr[i][1]]) {
que[ended++] = arr[i][1];
cnt[arr[i][1]] = cnt[val] + 1;
}
if (arr[i][1] == val && !visited[arr[i][0]]) {
que[ended++] = arr[i][0];
cnt[arr[i][0]] = cnt[val] + 1;
}
}
}
}
int main() {
cin >> n;
cin >> x >> y;
cin >> m;
for (int i = 0; i < m; i++)
cin >> arr[i][0]>>arr[i][1];
bfs();
if (cnt[y]==0) {
cout << -1 << endl;
return 0;
}
cout << cnt[y] << endl;
return 0;
}
아이디어자체를 생각하는게 어려운 문제였습니다. 구현난이도는 굉장히 낮구요.
'알고리즘 > BFS' 카테고리의 다른 글
| [백준] 9205-맥주 마시면서 걸어가기(C++) (0) | 2020.03.12 |
|---|---|
| [백준] 5014-스타트링크(C++) (1) | 2020.03.12 |
| [백준] 2589-보물섬(C++) (0) | 2020.03.08 |
| [백준] 7562-나이트의 이동(C++) (0) | 2020.03.08 |
| [백준] 7569-토마토(C++) (0) | 2020.03.05 |
