https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어
www.acmicpc.net
#문제 간단 정리
dfs 혹은 bfs를 사용하자
#문제 해결 방법
dfs를 사용해서 depth를 반환하도록 해줬다.
근데 만들고 나니 result = min(result, curResult); 로 최소 거리를 확인해 줘야 되서
bfs 로 풀면 더 쉽게 풀거라는 생각이 들었따.
#전체 코드
dfs 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
bool check[103];
int dfs(int node, vector<vector<int>>& families, int depth, int target) {
if (node == target) {
return depth;
}
check[node] = true;
int result = INT_MAX;
for (int i = 0; i < families[node].size(); i++) {
int next = families[node][i];
if (!check[next]) {
int curResult = dfs(next, families, depth + 1, target);
if (curResult != -1) {
result = min(result, curResult);
}
}
}
return result == INT_MAX ? -1 : result;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
int start, target;
cin >> start >> target;
vector<vector<int>> families(N + 1);
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
families[x].push_back(y);
families[y].push_back(x);
}
fill_n(check, 103, false);
int result = dfs(start, families, 0, target);
cout << result << '\n';
return 0;
}
bfs 코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int bfs(int start, int target, vector<vector<int>>& families) {
vector<bool> visited(families.size(), false);
queue<pair<int, int>> q; // {노드 번호, 촌수}
q.push({start, 0}); // 시작 노드와 촌수 0부터 시작
visited[start] = true;
while (!q.empty()) {
int current = q.front().first;
int distance = q.front().second;
q.pop();
if (current == target) {
return distance;
}
for (int next : families[current]) {
if (!visited[next]) {
visited[next] = true;
q.push({next, distance + 1});
}
}
}
return -1; // 목표 노드에 도달할 수 없는 경우
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
int start, target;
cin >> start >> target;
vector<vector<int>> families(N+1);
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
families[x].push_back(y);
families[y].push_back(x);
}
int result = bfs(start, target, families);
cout << result << '\n';
return 0;
}'[백준] > C++' 카테고리의 다른 글
| 백준 1920번 수 찾기 [C++] (0) | 2024.03.24 |
|---|---|
| 백준 7579번 앱 [C++] (0) | 2024.03.20 |
| 백준 2473번 세 용액 [C++] (0) | 2024.03.17 |
| 백준 1806 부분합 [C++] (0) | 2024.03.13 |
| 백준 20040번 사이클 게임 [C++] (0) | 2024.03.10 |
