위상정렬4 백준 2611번 : 자동차경주 (Java) 문제 https://www.acmicpc.net/problem/2611 2611번: 자동차경주 첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p ,q ,r의 형식으로 도로의 정보가 주어 www.acmicpc.net 구현 방법 최근 위상 정렬 알고리즘을 밀고 있어 위상 정렬임을 알고 풀었는데 만약 몰랐다면 무슨 알고리즘 사용할지 꽤나 고민을 했을 것 같습니다. 다익스트라랑 비슷한 느낌일 수 있는데 다익스트라는 도달한 노드는 거리값이 확정됩니다. 하지만 자동차경주는 도달해도 그 값이 최대값인지 보장되지 않아 해당 노드까지 도달하는 모든 노드들을 비교해야하므로 위상정렬을 사용해야 합니다. 저는 점수.. 2022. 2. 11. 백준 2637번 : 장난감 조립 (Java) 문제 https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 구현 방법 완제품을 조립하는데 필요한 기본 부품의 수를 구해야 합니다. 완제품을 조립하기 위해서는 중간 부품과 기본 부품들이 필요한데 중간 부품은 또 다른 중간 부품과 기본 부품으로 구성될 수 있습니다. 기본 부품부터 시작하여 기본 부품을 사용하는 중간 부품 -> 중간 부품과 기본 부품을 사용하는 중간 부품 -> 중간 부품과 기본 부품을 사용하는 완제품의 순서를 지.. 2022. 2. 11. 백준 9470번 : Strahler 순서 (Java) 문제 https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 구현 방법 Strahler순서를 구하려면 들어오는 강들을 모두 거친 후 들어와야 하기 때문에 위상 정렬 알고리즘을 사용했습니다. Strahler는 하천 순서로 항상 바다와 만나는 노드인 M의 Strahler 순서를 출력해주면 됩니다. 강을 들어갈 때마다 순서와 개수를 저장해야 하기 때문에 1. 노드 번호(강 번호)를 저장할 변수 2. 강의 순서 중 가장 큰 값을 저장할 변수 3. 가장 큰.. 2022. 2. 10. 백준 14567번 : 선수과목 (Prerequisite) (Java) 문제 https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 구현 방법 위상 정렬의 대표적인 문제입니다🥶 위상 정렬 (Topology Sort) 이란 방향 그래프에 존재하는 각 정점들의 선행 순서를 배신하지 않으면서 모든 정점을 나열하는 것 입니다. bfs를 이용한 위상정렬의 기본적인 해결 방법 입니다. 1. 진입 차수가 0인 정점을 큐에 저장 2. 선택된 정점과 부속된 간선 삭제 3. 모든 정점이 선택되거나 삭제 될 때까지 위 과정 반복 여기에 이수 학기를 계산해야 했기 때문.. 2022. 2. 9. 이전 1 다음
