본문 바로가기

DFS5

[백준_그래프] DFS와 BFS 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. .. 2024. 2. 1.
[백준_그래프] 2606번 - 바이러스 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수.. 2024. 2. 1.
[백준_그래프] 24479번 - 알고리즘 수업 - 깊이 우선 탐색 1 문제 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 오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자. 깊.. 2024. 1. 31.
[자료구조] DFS와 BFS의 비교 DFS vs. BFS: 그래프 탐색 알고리즘 비교 그래프 탐색은 그래프나 트리와 같은 자료구조에서 노드를 탐색하는 중요한 작업입니다. 이러한 탐색을 수행하기 위해 주로 사용되는 두 가지 알고리즘인 "깊이 우선 탐색 (DFS)"와 "너비 우선 탐색 (BFS)"를 비교해보겠습니다. [자료구조] DFS 이란? 깊이 우선 탐색 (DFS) 이란? 깊이 우선 탐색(DFS, Depth-First Search)은 그래프와 트리와 같은 자료구조에서 사용되는 탐색 알고리즘 중 하나입니다. 이 알고리즘은 어떤 시작 노드에서 출발하여 가능한 sonlife97.tistory.com [자료구조] BFS 이란? 너비 우선 탐색 (BFS) 이란? 너비 우선 탐색(BFS, Breadth-First Search)은 그래프와 트리와 같은.. 2024. 1. 23.
[자료구조] DFS 이란? 깊이 우선 탐색 (DFS) 이란? 깊이 우선 탐색(DFS, Depth-First Search)은 그래프와 트리와 같은 자료구조에서 사용되는 탐색 알고리즘 중 하나입니다. 이 알고리즘은 어떤 시작 노드에서 출발하여 가능한 한 깊이 들어가서 더 이상 진행할 수 없을 때까지 탐색을 진행한 후, 다음 분기로 넘어가는 방식을 취합니다. DFS의 주요 특징 1. 재귀 또는 스택 사용 DFS는 주로 재귀 함수 호출 또는 스택을 사용하여 구현됩니다. 각 노드를 방문하면 스택에 현재 노드를 추가하고, 더 이상 진행할 수 없을 때 스택에서 이전 노드로 돌아갑니다. 2. 깊이 우선 DFS는 한 분기를 깊이 탐색하며, 더 이상 진행할 수 없을 때까지 계속 진행합니다. 따라서 가장 깊이 있는 노드를 먼저 탐색하고 나중에 돌아옵.. 2024. 1. 23.

티스토리툴바