위상정렬 검색 결과
3 개의 검색 결과가 있습니다.
개발/알고리즘

[백준 9470] Strahler 순서 (python)

9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 위상정렬을 이용하여 푼다. [진입차수, 최대레벨, 최대레벨개수]를 나타내는 indegree 배열을 생성한다. 간선들은 ndict에 저장한다. 진입차수(indegree[i][0])가 0인 정점들을 queue 에 넣고 최대레벨(indegree[i][1])을 1로 설정해준다. queue에서 뽑아 해당 정점과 연결되어있는 정점들의 진입차수들을 1씩 낮춰주면서 최대레벨과 최대레벨개수를 갱신해준다. 만약 차수가 0이 된다면 최대레벨 개수가 2이상이라면 최대레벨을 1 올..

2021. 5. 31. 01:50
개발/알고리즘

[백준 1516] 게임 개발(python)

1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상정렬을 사용하자! 5 10 -1 10 1 -1 4 1 -1 4 3 1 -1 3 3 -1 입력을 받으면서 필요한 재료건물을 arr배열에 기록하고, 진입차수(indegree)를 update해준다. 진입차수가 0이라면 필요한 재료들을 다 만들어졌다는 뜻으로 queue에 넣어준다. queue를 돌면서 건물을 완성할때 해당 건물이 재료가 되는 건물 진입차수를 1 줄여준다. 재료건물들은 동시에 여러개 생성할 수 있으므로 제일 오래 걸리는 재료건물시간을 더해준..

2021. 5. 4. 23:31
개발/알고리즘

[백준 2252] 줄 세우기 (python)

2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 위상 정렬을 이용한다. s -> e 순으로 와야할때 e의 진입차수는 1이라고 한다. 수들의 관계를 저장할 ndict를 생성한다. 진입 차수들을 저장하는 indegree를 생성한다. 수들을 입력받으면서 ndict와 indegree를 update해준다. 입력차수가 0인 수들을 queue에 넣는다. queue에서 빼면서 해당 숫자에 연결되어 있는 숫자들의 입력 차수를 1빼준다. 만약 입력차수가 0이 되었다면 queue에 넣어준다. im..

2021. 5. 3. 21:51