문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다. 6 8 2 6 2 3 2 3 4 6 7 2 5 3 6 8 9 5 2 7 이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모..
DFS
문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수..
알고리즘은 컴퓨터 과학의 핵심 개념 중 하나로, 문제를 해결하기 위한 절차적인 방법을 의미한다. 이 중에서도 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그 중요성과 유용성으로 널리 사용되는 탐색 알고리즘이다. 이 두 가지 알고리즘은 트리나 그래프와 같은 자료구조에서 매우 중요하게 사용되며, 여러분의 알고리즘 공부를 위한 핵심 개념 중 하나로 꼽힌다. 1. 깊이 우선 탐색(DFS) 깊이 우선 탐색은 그래프에서 한 노드를 시작으로 연결된 모든 노드를 탐색한 후, 다음 노드로 넘어가기 전까지 깊이를 최대한 탐색하는 방식이다. 이러한 특성으로 인해 재귀적인 방법이 주로 사용되며, 스택 자료구조를 이용해서도 구현할 수 있습니다. DFS는 미로 찾기와 같이 경로를 탐색하는 문제나 그래프의 연결성을 확인하..
