BAEKJOON/그래프
백준 2617번 [구슬 찾기](C++) -yes6686- 티스토리
yes6686
2025. 7. 7. 00:45
728x90
반응형
SMALL
백준 문제 풀이: 2617 (구슬 찾기)
문제 링크: https://www.acmicpc.net/problem/2617
문제 설명:
각 구슬의 무게가 서로 다르며, 일부 구슬들 사이의 비교 결과가 주어졌을 때, 특정 구슬의 무게가 전체에서 중간이 아님을 판별하는 문제입니다. 즉, 어떤 구슬이 n개의 구슬 중 정확히 중간보다 무거운지/가벼운지를 확정할 수 없는지를 판별합니다.
구슬 수 N(≤100), 비교 결과 수 M(≤N(N-1)/2)이 주어지고, 모든 구슬을 대상으로 탐색하면서 절반 이상 무겁거나 가벼운 구슬 수를 구해 조건에 만족하면 해당 구슬은 중간이 될 수 없습니다.
문제 해결 코드
// 구슬 찾기 (양방향 DFS 탐색)
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
vector<int> v1[101]; // 더 무거운 쪽
vector<int> v2[101]; // 더 가벼운 쪽
int visited[101];
int dfs(int x, vector<int> v[]) {
int cnt = 0;
for (int i = 0; i < v[x].size(); i++) {
int k = v[x][i];
if (visited[k]) continue;
visited[k] = 1;
cnt += dfs(k, v);
}
return cnt + 1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
v1[a].push_back(b); // a > b
v2[b].push_back(a); // b < a
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int half = n / 2;
visited[i] = 1;
int heavier = dfs(i, v1) - 1; // 자신보다 무거운 구슬
memset(visited, 0, sizeof(visited));
visited[i] = 1;
int lighter = dfs(i, v2) - 1; // 자신보다 가벼운 구슬
memset(visited, 0, sizeof(visited));
if (heavier > half || lighter > half) {
ans++;
}
}
cout << ans << '\n';
}
코드 설명
- 핵심 알고리즘: DFS를 통해 각 정점(i번 구슬)에서 자신보다 무거운/가벼운 구슬 개수를 구합니다. 이때 n/2보다 크면 중간이 될 수 없습니다.
- 구현 세부사항:
v1[i]
: i번 구슬보다 가벼운 구슬들 (i > j)v2[i]
: i번 구슬보다 무거운 구슬들 (j > i)- 두 번의 DFS 후, 무겁거나 가벼운 구슬이 절반을 넘는 경우 카운트
- 시간 복잡도 분석: O(n ⋅ (n + m)), 각 정점마다 DFS를 수행하므로 최대 100⋅(100+M) 내외의 탐색으로 충분히 통과됩니다.
결과
중간이 될 수 없는 구슬의 개수를 출력합니다.
예시 입력:
5 4
1 2
3 2
4 2
5 2
예시 출력:
1
이 문제는 위상 정렬, DFS 등 탐색 알고리즘의 기초 응용 문제로, 그래프 구조 분석 능력을 기르기에 매우 좋습니다. 다른 풀이 아이디어가 있다면 댓글로 공유해주세요!
728x90
반응형
LIST