DFS깊이우선탐색

DFS란

그래프 완전탐색 기법중 하나, 그래프의 시작노드에서 출발하여 한 분기의 최대깊이 까지 탐색을 마친후 다른 분기의 탐색을 진행한다.

알고리즘

다음과 같은 그래프가 있다고 할 때

1. 초기작업

• 그래프를 ArrayList배열로 표현하기

  1번노드 – 2, 3
   2번노드 - 4
   3번노드 - 1
   4번노드 - 2

  위와 같은 연결리스트배열을 통해 표현 할 수 있다.

• 방문배열 초기화하기
  이미 방문했던 노드를 다시 방문하지 않기위해 boolean배열을 생성한다.

2. 탐색과정

   시작노드가 1번 노드일때

1) 노드1과 연결된 노드2를 방문후 방문 배열에 체크(이때 방문할 노드의 순서는 상관없다)

2) 노드2와 연결된 노드4를 방문후 방문 배열에 체크

3) 노드4에서 노드2는 이미 방문했으므로 1번노드로 되돌아가 노드 3에서 다시 탐색시작

4) 위의 과정과 같이 모든 노드를 방문 할 때까지 반복한다.

구현코드

1. 백준13023
   탐색 깊이가 5이상이 넘어가면 1, 아니면 0을 출력하는 문제

재귀함수 중간에 깊이가 5가 나와 종료하는 경우 flag변수를 통해 전체 재귀를 종료하도록 구현함

public class Q25 {
	
	static ArrayList<Integer>[] arr;
	static boolean[] visit ;
	static boolean flag = false;
	 
	public static void main(String[] args) throws Exception{
		
		BufferedReader in= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		
		int people = Integer.parseInt(st.nextToken());
		int relation = Integer.parseInt(st.nextToken());
		
		arr = new ArrayList[people];
		visit = new boolean[people];
		
		for(int i=0; i<people; i++) {
			arr[i] = new ArrayList<Integer>();
		}
		
		for(int i=0; i<relation; i++) {
			st = new StringTokenizer(in.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			arr[a].add(b);
			arr[b].add(a);
		}
		for(int i=0; i<people; i++) {
			if(visit[i] == false) {
				DFS(i, 1);
			}
			if(flag) {
				break;
			}
		}
		
		if(flag) {
			System.out.println("1");
		}
		else {
			System.out.println("0");
		}
	}
	
	public static void DFS(int n, int depth) {
		if(depth == 5 || flag) {
			flag = true;
			return; 
		}
		
		if(visit[n]) {
			return;
		}
		visit[n] = true;
		for(int i: arr[n]) {
			if(visit[i] == false) {
				DFS(i, depth+1);
			}
		}
	}
}

2. 백준 2023 신기한 소수를 찾는 문제

   DFS알고리즘은 데이터를 그래프로 표현하여 탐색하는 경우 뿐 아니라
   모든 경우의 수를 탐색하면서 가지치는 문제를 풀 때 적용가능하다.

public class Q24 {
	static int n;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();

		DFS(2,1);
		DFS(3,1);
		DFS(5,1);
		DFS(7,1);
		
	}

	public static void DFS(int num, int jarisu) {
		boolean sosu = true;
		for(int i=2; i<=Math.sqrt(num); i++) {
			if(num%i == 0) {
				sosu = false;
			}
		}
		
		if(jarisu == n) {
			if(sosu) {
				System.out.println(num);
			}
		return;
		}
		
		if(sosu == false)return;
		
		for(int i=1; i<=9; i++) {
			if(i%2 != 0) DFS(num*10 + i ,jarisu+1);
		}
		
	}
}