개발하는 고라니

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net # 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. (한 배추의 ..

그래프에서 모든 정점을 방문하는 방법 중 하나인 너비 우선 탐색(Breadth-First Search, BFS)에 대해 공부하고자 한다. 그래프의 모든 정점을 방문하는 방법인 DFS와 BFS는 간단하지만 그래프의 알고리즘에서 핵심적인 위치를 차지한다. 따라서 반드시 알아야 할 알고리즘들 중 하나이며, 코딩테스트에도 빈번히 출제되는 유형이다. 루트를 시작으로 탐색을 한다면 BFS는 먼저 루트의 자식을 차례로 방문한다. 다음으로 루트의 자식의 자식, 즉 루트에서 두 개의 간선을 거쳐서 도달할 수 있는 정점을 방문한다. 또 다음으로 루트에서 세 개의 간선을 거쳐서 도달할 수 있는 정점들 순으로 루트에서 거리 순으로 방문한다. (거리에 따라 단계별로 탐색한다.) BFS는 두 노드 사이의 최단 경로(멀리 떨어진 ..

그래프에서 모든 정점을 방문하는 방법 중 하나인 깊이 우선 탐색(Depth-First Search, DFS)에 대해 공부하고자 한다. 그래프의 모든 정점을 방문하는 DFS와 BFS는 간단하지만 그래프의 알고리즘에서 핵심적인 위치를 차지한다. 따라서 반드시 알아야 할 알고리즘들 중 하나이며, 코딩테스트에도 빈번히 출제되는 유형이다. 이와 더불어 너비 우선 탐색(Breadth-First Search, BFS)도 있다. 이는 다음에 공부해보도록 한다. DFS는 BFS에 비해 구현이 간단하나, 검색 자체 속도는 BFS보다 느린 편이다. DFS는 루트(Root)의 자식 정점을 하나 방문한 다음 아래로 내려갈 수 있는 곳 까지 내려간다. 더 이상 내려갈 수 없으면 위로 되돌아오다가 내려갈 곳이 있으면 즉각 내려간다..