https://www.acmicpc.net/problem/32251시간 제한메모리 제한2초(추가 시간 없음)1024MB(추가 메모리 없음)문제목이 마른 나무에게 물을 주자! 나무는 N개의 정점과 (N-1)개의 간선으로 이루어져 있으며, 어느 두 정점 간에도 단순 경로가 유일하게 존재하는 그래프를 의미한다. 1번 정점을 나무의 뿌리라고 부르자. 또 i번 정점과 직접 연결되어 있으면서 뿌리와의 단순 경로의 길이가 i번 정점보다 더 큰 정점을 i번 정점의 자식 정점이라고 부르자. 각 정점에는 열매가 하나씩 있다. 열매에 물을 주면 자신의 크기만큼 물을 흡수할 수 있고, 물을 주면 가능한 최대로 흡수한다. 또한 흡수한 물의 양만큼 열매의 크기가 커진다. 자식 정점이 하나 이상 있다면, 열매가 흡수하고 남은 물은..

1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 1번부터 시작해야겠다. 모든 정점 V가 범위 내의 정점 V + 1, V - 1, V * 2 와 연결되어있고 가중치는 1이다. BFS로 탐색을 시작해서 찾는대로 시간을 출력하게 하면 될 것 같다. using System; using System.Collections.Generic; class Program { static int n, k; static int[] time = new int[100001]; static bool[]..

BFS는 그래프나 트리의 자료구조에 적용할 수 있는 맹목적 탐색 알고리즘이다. 맹목적 탐색은 주어진 정보에 따라 효율적인 탐색을 실시하는 것이 아닌 이미 정해진 순서로 탐색을 실시하는 방법으로 실용적으로 따져볼 때 매우 비효율적인 알고리즘이지만 구현이 쉽고 간단한 문제에 한해 아주 유용하다. 이름 그대로 트리에서 노드를 깊게 파고드는 것보다 한 계층을 순차적으로 모두 살펴보는 것을 우선하는 알고리즘이다. BFS는 Queue로 구현할 수 있다. 1. 탐색을 시작할 정점을 Queue에 삽입한다. 2. Queue가 비었다면 '9'로 이동한다. 3. Queue의 가장 위에 있는 정점이 현재 탐색 중인 정점이다. 4. 탐색 중인 정점이 찾으려는 자료이면 '8'로 이동한다. 5. 탐색 중인 정점과 연결된 정점을 Q..

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net IDEA 두 알고리즘은 이름에서 나타내는 것처럼 탐색의 우선순위가 다르다. 최초 탐색 지점에서 연결된 곳들을 순차적으로 확인하는 너비우선탐색(BFS)은 한 계층의 정점을 모두 확인하고 다음 계층으로 내려가기 때문에 최단거리를 찾는 탐색에서 유리하다. 깊이우선탐색(DFS)은 탐색 경로를 기억해둬야할 때 유리하다. 모든 정점을 탐색해야하는 문제에서는 어떤 알고리즘을 선택해도 시간복잡도 상의 차이는 없다. 이 문제는 모든 정점을 탐색해야하는 문제이기 때문에 너비우선탐색, 깊이우선..