그래프4 [Baekjoon] 1260번: DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 해결 과정 착안 문제에서 주어지는 간선 정보를 바탕으로 깊이 우선 탐색(depth-first search, DFS)과 너비 우선 탐색(breadth-first search, BFS) 알고리즘을 구현하는 것을 요구하는 문제이므로, 두 알고리즘의 특징에 유의하여 구현하고자 하였다. 깊이 우선 탐색 알고리즘은 스택(stack) 자료 구조를 활용하여 구현(또는 .. 2023. 5. 8. [Baekjoon] 24444번: 알고리즘 수업 - 너비 우선 탐색 1 https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 문제 해결 과정 착안 간선(edge)의 가중치가 모두 일정한 무향(undirected) 그래프(graph) 자료 구조에서의 너비 우선 탐색 알고리즘(breadth-first search, BFS)을 구현하는 문제이므로, 간단한 그래프 클래스와 문제에서 요구하는 너비 우선 탐색 알고리즘을 구현하였다. 이번에도 한 정점에 대한.. 2023. 5. 7. [Baekjoon] 2606번: 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 해결 과정 착안 문제를 보자마자 그래프 자료구조를 이용해 시작 정점으로부터 연결되어 있는 모든 정점을 순회하는 알고리즘인 깊이 우선 탐색 알고리즘(depth-first search, DFS), 또는 너비 우선 탐색 알고리즘(breadth-first search, BFS)을 이용해야할 것으로 판단되었다. 마침 지난 포스트에서 깊이 우선 탐색 알고리즘을 구현했었던 것을 활용(...)하여, 해당 코드를.. 2023. 5. 7. [Baekjoon] 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 문제 해결 과정 착안 간선(edge)의 가중치가 모두 일정한 무향(undirected) 그래프(graph) 자료 구조에서의 깊이 우선 탐색 알고리즘을 구현하는 문제이므로, 간단한 그래프 클래스와 문제에서 요구하는 깊이 우선 탐색(depth-first search, DFS) 알고리즘을 구현하였다. 이때, 한 정점에 대한 간선의.. 2023. 5. 7. 이전 1 다음
