boj 10159: 저울

https://www.acmicpc.net/problem/10159

10159번: 저울

 

진짜 오랜만에 포스트를 한다. 이제 주기적으로 문제를 풀기로 마음을 먹었다.

이 문제는 태그가 floyd이다. 근데 다르게 풀었다. floyd는 다른 사람 풀이를 참조해야 겠다...

기본적으로 이것도 n^3 이긴 한데 그냥 위상정렬 + dfs로 풀었다.

위와같이 6은 input edge가 0개이므로 ind=0으로 두었다.

각 노드와 비교가 불가능한 노드는 총 몇개인지를 구해야 하는데, 1을 예로 들자. 우선 비교할 수 있는걸 구해보자.

위 상황에서 6과 2와 3에서 1로 다다를 수 있으므로 각각 1씩 카운트를 해주어야 한다. 마찬가지로 1에서 reach 할 수 있는 노드들 카운트도 해주어야 한다. 이 모든 카운트된 값들을 N에서 빼준값이 답이 된다. 전자의 경우에는 1보다 먼저 위상정렬상 앞순위의 노드들부터 dfs 탐색하면서 카운트를 해줄 수 있다.  그것이 밑부분인 ans[p]++부분이다.

그리고 각 노드에서 reach 할 수 있는 노드들 갯수 (시작노드포함) 은 res로 계산해주면 된다.

만약 해당 노드가 ind값이 0이라면, 이 노드를 시작으로 위상정렬을 해준다. 6에서 시작하면 2, 3, 1, 9, 7를 1씩 카운트 먹여주고, 본인은 사라지면 된다.(6->2, 6->3, 6->7삭제) 그리고 완료했다는 의미로 check 표시를 해준다. (while내에 for문 순회하면서 만약 안해주면 이미 한걸 다시 할 수 있기때문이다.) 

 

#include<bits/stdc++.h>

using namespace std;


int n,m,from,to,ind[101],ans[101];
bool check[101], visited[101];
vector<int> edge[101];

int proc(int v){
  int res = 1;
  bool done = false;
  visited[v] = true;
  for(auto& p : edge[v]){
    if(!visited[p]){
      ans[p]++;
      res += proc(p);
      done = true;
    }
  }
  if(!done) return 1;
  return res;
}

int main(){

  memset(ind,0,sizeof(ind));
  memset(ans,0,sizeof(ans));
  memset(check,false,sizeof(check));
  cin>>n;
  cin>>m;
  for(int i = 0; i < m; i++){
    cin>>from>>to;
    edge[from].push_back(to);
    ind[to]++;
  }
  while(1){
    bool done = false;
    for(int v = 1; v <= n; v++){
      memset(visited,false,sizeof(visited));
      if(!ind[v] && !check[v]){
        done = true;
        ans[v] += proc(v);
        for(auto &p: edge[v]){
          ind[p]--;
        }
        check[v] = true;
      }
    }
    if(!done) break;
  }

  for(int i = 1; i <= n; i++){
    cout<<n-ans[i]<<'\n';
  }



  return 0;
}