Jumping to the water

▶ 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net ▶ 설명 1이 몇개씩 모여있는지 오름차순으로 출력하는 문제이다. 먼저, 2차 배열로 0과 1의 값을 입력 받는다. 이 2차 배열 요소를 모두 탐색하며 1인 곳에서 DFS혹은 BFS로 탐색을 이어나가고, 0인 곳은 그냥 지나가게 한다. DFS를 (혹은 BFS) 사용할 때 다음 노드로 탐색을 이어가기 위해서는 좌,우,위,아래의 위치를 통해 배열의 범위 밖을 넘어가는 위치, 혹은 원소 값이 0일..

▶ 문제 https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net ▶ 설명 이전 글에서 다뤘던 깊이 우선 탐색1 에서 정렬 조건만 달라진 변형된 문제이다. 예제를 그래프로 그리면 위와 같이 나타낼 수 있는데 노드마다 연결된 노드들을 나열하면 다음과 같다. 노드1 : 4, 2 노드2 : 1, 3, 4 노드3 : 2, 4 노드4 : 1, 2, 3 노드5 : x (연결된 노드 없음) 노..

▶ 문제 https://www.acmicpc.net/problem/24479 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와 bfs 가 있다. DFS 는 Depth First Search(깊이 우선 탐색)의 약자로, 노드를 탐색하는 방향이 넓게 가는 것이 아니라 깊숙이 들어간다는 특징이 있고, Stack 의 자료구조가 녹아져 있다. 그러나 실제 코드에서는 stack 이 아닌 재귀함수로 구현된다. ..