boj 10159: 저울

boj 10159: 저울

https://www.acmicpc.net/problem/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 using namespace std; int n,m,from,to,ind[101],ans[101]; bool check[101], visited[101]; vector 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<

'; } return 0; }

from http://zensen6-it.tistory.com/30 by ccl(A) rewrite - 2021-08-26 01:00:19