공부하는 블로그

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 깊이우선탐색(DFS)를 이용해서 아파트 단지가 몇개인지, 각 단지에는 아파트가 몇개인지 찾는 문제이다. import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Main { static int N; // 지도의 크기 static int[][] map; // 지도 static boolean[][] visit; // 방문 여부 저장 static int..

DFS와 BFS는 그래프를 탐색하는 방법이다. 둘의 차이를 간단히 말하자면 깊이(자식)를 우선으로 탐색하냐, 너비(형제)를 우선으로 탐색하냐 이다. DFS (Depth First Search) 깊이 우선 탐색(DFS)은 루트(root) 노드 또는 임의의 노드를 기준으로 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 즉, 한 곳을 선택하여 우선적으로 끝까지 탐색한 후에야 다른 인접한 노드를 방문할 수 있다. 이 방법은 그래프의 모든 노드를 방문하고자 할 경우 유용하다. 코드로 구현할 때에는 스택(stack)과 재귀함수를 사용한다. 재귀함수를 이용하여 DFS를 구현하는 과정은 다음과 같다. * 재귀함수 : 자기 자신을 호출하는 함수 0. 시작 노드가 없을 경우에는..