목록 위상정렬 (2)
반응형

Stargazer

[백준(BOJ)] 2623번 : 음악 프로그램 C++ 풀이(위상정렬)

접근: 노드간 순서를 정렬하는 것이기 때문에, 위상정렬로 해결하면 된다. 전략: 각 순서에 대해서 그래프를 그려주고, 그래프 중에서 진입차수가 0인 노드부터 처리하면서, 그 노드로 부터 진입하는 노드의 진입차수를 하나 씩 줄여간다. 그리고 줄인 차수 중 0인 노드를 다시 탐색하면서 반복한다. 만약 처리하지 못한 노드가 있는데, 진입차수가 0인 것이 없다면 순서를 처리 할 수 없는 상태이고, 처리 수랑 전체 노드 수가 같다면, 그 처리 순서대로 출력하면 된다. 코드: #include #include #include using namespace std; int n,m; vector edge[1002]; int num[1002]; int main(){ cin >> n >> m; for(int i=0;i> t;..
Undergraudate basics(학부생 기초)/자료구조, 알고리즘 2022. 7. 31. 16:49
[백준] 2252번 : 줄 세우기 C++ (위상정렬)

접근: 처음에는 어떻게 접근 해야 할지 직접 그려보면서, 관계를 파악해보았다. 대충 봐도 그래프 이론으로 풀어야 하는데, 그 중 순서 정렬이 필요하기 때문에 위상 정렬로 풀어야 한다는 걸 알 수 있다. 전략: 대소 관계를 표현하기 위해 입력을 digraph(유향그래프) 형태로 입력을 받는다.(형식은 자유 - 행렬, 인접리스트) 진입 차수가 0인 노드부터 큐에 넣고, 큐에서 하나씩 제거하면서 출력한다. 제거한 노드가 가리키는 다른 노드의 진입 차수를 한개 줄이고, 만약 0이라면 큐에 삽입한다. 코드: #include #include #include using namespace std; int n,m; vector comp; vector income; int main(){ cin >> n >> m; comp..
Undergraudate basics(학부생 기초)/자료구조, 알고리즘 2022. 7. 5. 14:08
Prev 1 Next