백준 10159 - 저울(C++)

문제 링크입니다. https://www.acmicpc.net/problem/10159

10159번: 저울

플로이드 와샬 혹은 DFS를 이용해 풀 수 있던 문제입니다.

플로이드 와샬로 푸는 문제였지만, DFS를 이용하면 더 쉽게 풀 수 있었습니다.

 

1~N번까지 무게의 비교가 주어질 때, X번 물건과 비교할 수 없는 물건이 몇개인지를 구하는 문제였습니다.

그렇다면, 전부 비교할 수 없다면 값은 N-1이 될 것입니다.

 

여기서, 자신보다 큰 물건과 작은 물건의 갯수만 알고 있다면 N-1에서 두 수를 빼준 값이 정답이 된다는 것을 알 수 있습니다.

 

따라서, 저는 X번 물건보다 크거나 작은 물건의 갯수를 찾고, 이를 빼줘서 답을 구하는 방법으로 풀었습니다.

 

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
#define INF 987654321

using namespace std;

int N, M, cnt;
vector<int> up[101];
vector<int> down[101];
int check[101];

void dfs(vector<int> v[], int start){
    check[start] = 1;
    for(int i = 0; i < v[start].size(); i++){
        int x = v[start][i];
        if(check[x] == 0){
            cnt++;
            dfs(v, x);
        }
    }
}

void solve(){
    for(int i = 1; i <= N; i++){
        cnt = 0;
        memset(check, 0, sizeof(check));
        dfs(up, i);
        memset(check, 0, sizeof(check));
        dfs(down, i);
        cout << N - cnt - 1 << "\n";
    }
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        int x, y;
        cin >> x >> y;
        up[x].push_back(y);
        down[y].push_back(x);
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요