본문 바로가기

위상 정렬

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

CodingTEST 2023. 8. 29. [백준 1516] 게임 개발 (JAVA) 백준 1516번 문제 - 게임 개발 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제 분석 건물을 짓기 위해 선행되어야하는 건물이 있다. 그럼 이 건물을 짓기 위해 필요한 최소 시간을 출력한다. 2, 3 둘 다 1번 건물이 필요할 때 : 1번 짓고 2번 1번 또 짓고 3번이 아니라, 1번 짓고 2, 3을 짓는 것으로 시간을 잰다. 해결 키 포인트 위상 정렬 개념 이해 위상 정렬할 때, inDegree 배열에 선행되어야 할 건물 개수가 아닌 자신이 선행되어야하는 건물의 개수로 한다. 현재 이미 건..

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

CodingTEST 2023. 8. 27. [백준 2252] 줄 세우기 (JAVA) 백준 2252번 문제 - 줄 세우기 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 분석 N(학생 수), M(비교 횟수) 입력 M번의 비교 입력 : a b 입력 - a가 b의 앞에 와야한다 이를 토대로 학생들 나열 순서에 맞춰 출력해라 해결 키 포인트 위상 정렬 개념 이해 위상 정렬 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으..

이전 1 다음

티스토리툴바