본문 바로가기

BFS6

[백준_그래프] 2178번 - 미로 탐색 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력.. 2024. 2. 1.
[백준_그래프] 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.
[자료구조] 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.
[자료구조] BFS 이란? 너비 우선 탐색 (BFS) 이란? 너비 우선 탐색(BFS, Breadth-First Search)은 그래프와 트리와 같은 자료구조에서 사용되는 탐색 알고리즘 중 하나입니다. 이 알고리즘은 시작 노드에서부터 인접한 모든 노드를 먼저 탐색하고, 그 다음 레벨의 노드로 넘어가며 탐색을 진행합니다. 즉, 깊이보다 너비를 우선으로 탐색하는 방식입니다. BFS의 주요 특징 1. 큐(queue) 사용 BFS는 큐 자료구조를 사용하여 구현됩니다. 시작 노드를 큐에 넣고, 큐가 빌 때까지 노드를 하나씩 빼면서 탐색을 진행합니다. 2. 너비 우선 BFS는 한 레벨의 모든 노드를 먼저 탐색하며, 그 다음 레벨로 넘어갑니다. 따라서 가장 가까운 노드부터 탐색하여 최단 경로 문제에 유용하게 사용됩니다. 3. 모든 노드 탐색 B.. 2024. 1. 23.
[이코테] 전보(2) - 코딩테스트 - 다른풀이 안녕하세요. 이번에는 이전에 풀었던 전보 - 다익스트라 알고리즘 풀이를 다른 방식으로 풀어보려고합니다. 다익스트라 풀이법은 아래의 링크로 들어가시면 보실 수 있습니다. https://sonlife97.tistory.com/entry/%EC%9D%B4%EC%BD%94%ED%85%8C-%EC%A0%84%EB%B3%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EA%B5%AC%EC%B2%B4%EC%A0%81%EC%9D%B8%ED%92%80%EC%9D%B4 [이코테] 전보 - 코딩테스트 - 구체적인풀이 문제 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하.. 2024. 1. 18.

티스토리툴바