반응형 위상정렬2 [백준/C++] 문제집 (No. 1766) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 위상정렬을 이용하고, 어떤 경우에 문제를 빨리 출력할지 구분하면 쉽게 해결할 수 있는 문제다. 조건에 따르면 더 쉬운 문제를 먼저 풀 수 있다면 먼저 풀어야 한다.그러므로 1번 문제부터 사전에 풀어야 하는 문제가 몇 개인지 파악한다. 이제 위상정렬을 떠올리면, i번 문제를 풀 수 있는 경우 i번 문제를 풂으로써 i번째를 사전에 풀어야하는 문제들은 사전에 풀 문제가 1개씩 줄어든다는 사실을 알 수 있다. 이를 이용해 for 문으로 1번 문제부터 사전에 풀어야 하는 문제가 0인지 미리 풀어야 하는 문제가 있는지 .. 2024. 7. 15. [백준/C++] 최종 순위 (No. 3665) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 풀기 전에 위상 정렬 문제를 풀었었다. 위상 정렬의 특징은 정렬할 때, 특정 노드로 들어오는 간선의 수를 이용하면 노드간의 상대적인 우선 순위를 이용해 정렬을 할 수 있다는 특징이 있었다. 그래서 이 문제도 위상정렬의 특징을 이용해 풀었다. 이 문제의 핵심은 모든 팀의 확실한 순위를 알게 되는지 판단하는 것이다. 확실한 순위를 알기 위해서는 처음에 특정 노드로 들어오는 간선이 0인 노드가 1개여야하며, 서로 다른 팀 간에 우선순위를 확실하게 알아야 하기 때문에 특정 노드에서 출발하는 간선을 하나씩 지울때 마다.. 2024. 7. 8. 이전 1 다음 반응형