문제 링크입니다: https://www.acmicpc.net/problem/2617
DFS(Depth First Search) 알고리즘을 이용해 해당 구슬보다 무겁거나 가벼운 구슬이 전체 구슬의 반 초과인지 확인하는 문제였습니다.
알고리즘은 아래와 같습니다.
1. 해당 구슬보다 무거운 구슬과 가벼운 구슬을 입력받습니다.
2. 1~N 번째 구슬을 모두 탐색하며 해당 구슬보다 무거운 구슬과 가벼운 구슬이 몇개인지 파악합니다.
3. 2번에서 구한 두 값 중 하나라도 전체 구슬의 반 초과이면 절대 중간에 있을 수 없습니다.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAX = 100;
int N, M;
vector<int> heavier[MAX], lighter[MAX];
bool hVisited[MAX], lVisited[MAX];
int HDFS(int node)
{
int result = 1;
for (int i = 0; i < heavier[node].size(); i++)
{
if (!hVisited[heavier[node][i]])
{
hVisited[heavier[node][i]] = true;
result += HDFS(heavier[node][i]);
}
}
return result;
}
int LDFS(int node)
{
int result = 1;
for (int i = 0; i < lighter[node].size(); i++)
{
if (!lVisited[lighter[node][i]])
{
lVisited[lighter[node][i]] = true;
result += LDFS(lighter[node][i]);
}
}
return result;
}
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < M; i++)
{
int marble1, marble2;
cin >> marble1 >> marble2;
heavier[marble1].push_back(marble2);
lighter[marble2].push_back(marble1);
}
vector<bool> result(N + 1);
for (int i = 1; i <= N; i++)
{
memset(hVisited, false, sizeof(hVisited));
memset(lVisited, false, sizeof(lVisited));
hVisited[i] = true, lVisited[i] = true;
//중간이 될 수 없는 조건
if (HDFS(i) > (N + 1) / 2)
result[i] = true;
if (LDFS(i) > (N + 1) / 2)
result[i] = true;
}
int cnt = 0;
for (int i = 0; i < N + 1; i++)
if (result[i])
cnt++;
cout << cnt << "\n";
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 1929번 소수 구하기 (0) | 2018.11.04 |
---|---|
백준 3184번 양 (0) | 2018.11.04 |
백준 2851번 슈퍼 마리오 (0) | 2018.11.04 |
백준 6581번 HTML (4) | 2018.11.03 |
백준 12761번 돌다리 (0) | 2018.11.02 |