BFS/DFS 검색 결과

해당 글 2건

[BOJ 24445] 알고리즘 수업 - 너비 우선 탐색 2 (C++)

알고리즘 수업 - 너비 우선 탐색 2 (Silver 2) 문제 전체 문제 보기 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 풀이 정점의 개수 N개만큼 정점을 만들고 각 정점에서 인접한 노드들을 먼저 방문하는 BFS를 구현하여서 푸는 문제. 다만, 인접한 노드를 방문할 때 인접한 노드 인덱스의 내림차순으로 방문해야 하기 때문에 인접한 노드 인덱스 값을 내림차순으로 정렬하는 단계가 필요함. 코드 #include #include #inclu..
Algorithms/DFS & BFS 2022. 5. 14. 09:19

[프로그래머스] (Greedy)섬 연결하기 (C++)

섬 연결하기 (Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 접근법 최소 비용 신장 트리 이번 문제는 두 가지 방법으로 풀었다. 처음 접근하는 방법은 동일하고 구현하는 방법에서 차이가 있기 때문에 공통된 부분을 설명한 뒤 두 가지 풀이법을 모두 다뤄본다. 문제에서 요구하는 바는 모든 섬을 가장 적은 비용으로 연결했을 때의 비용이다. 이를 자료구조에서는 최소 비용 신장 트리 (MST)라고 한다. 이에 대한 설명은 예전에 다룬 글이 있어 링크를 남긴다. 간략하게만 정리하면 최소 비용 신장 트리는 신장 트리의 일종인데, 먼저 신장 트리가 되기 위해서는 다음의 조건을 만족해야..
Algorithms/Greedy 2021. 7. 30. 12:21