[Algorithm] DFS, BFS

DFS 기본 로직 

key) 후입선출, 스택 자료구조 사용, 재귀 형태 

 

1. 시작 노드를 정한 후 사용할 자료구조 초기화

> 필요한 초기 작업은 무엇인가? 인접 리스트로 그래프 표현하기, 방문 배열 (visited) 초기화하기 

스택에 노드를 삽입할 때 visited T로 바꿔주는 것!

 

2. 스택에서 노드를 꺼낸 후, 꺼낸 노드의 인접 노드를 다시 스택에 삽입

이미 다녀간 노드는 재삽입하지 않는 것이 원칙임.

> 모든 노드를 다 돌 때까지 반복함.

 

백준 11724 연결 요소의 개수 

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

import java.io.*;
import java.util.*;

public class Main {
	static ArrayList<Integer>[] arr; 
	static boolean visited[];
	
	static void DFS(int s) {
		if(visited[s]) { 
			return; //리턴 조건. 
		}
		visited[s]=true; //방문했으니 true로 바꿔주기. 
		for(int a: arr[s]) {
			if(visited[a]==false) 
				DFS(a);
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); //정점
		int M = Integer.parseInt(st.nextToken()); //간선 
		
		arr = new ArrayList[N+1];
		visited = new boolean[N+1];
		
		for(int i = 1; i < N+1; i++) {
			arr[i] = new ArrayList<Integer>(); //인접 리스트 초기화
		}		
		
		for(int i = 0; i < M; i++) { //엣지 개수만큼 반복. 
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			//연결 요소의 개수는 그래프가 총 몇 덩어리(?)인지 
			arr[v].add(u);
			arr[u].add(v);			
		}
		
		int count = 0; //연결 요소 갯수 
		for(int i =1; i < N+1; i++) { //노드갯수만큼 반복
			if(!visited[i]) { //방문하지 않은 노드라면 
				count++;
				DFS(i); // i를 시작노드로 DFS 실행 
			}
		}
		System.out.println(count);
	}
		

}

 

백준 2023 신기한 소수

https://www.acmicpc.net/problem/2023

2023번: 신기한 소수

 

import java.io.*;
import java.util.*;

public class Main {
	static int n;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringBuilder sb = new StringBuilder();
//		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		
		DFS(2, 1);
		DFS(3, 1);
		DFS(5, 1);
		DFS(7, 1);
	}
	
	static boolean isPrimeNum(int num) {
		for(int i = 2; i<= num/2; i++) {
			if(num % i == 0) 
				return false;
		}
		return true;
	}
	
	static void DFS(int num, int j) { //j:자릿수
		if( j == n) {
			if (isPrimeNum(num)) {
				System.out.println(num);
			}
			return;
		}
		for(int i = 1; i <= 9; i++) {
			if( i % 2 == 0) 
				continue; //짝수는 탐색 X
			if(isPrimeNum(num*10 + i)) {
				DFS(num*10+i, j+1);
			}
		}
		
	}

}

 

백준 1260 BFS와 DFS

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

import java.io.*;
import java.util.*;

public class Main {
	static ArrayList<Integer> A []; //인접리스트
	static boolean visited[];
	static int n, m, v;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); //노드 개수
		m = Integer.parseInt(st.nextToken()); //에지 개수
		v = Integer.parseInt(st.nextToken()); //시작점 
		
		A = new ArrayList[n+1];
		
		
		for(int i = 1; i < n+1; i++) {
			A[i] = new ArrayList<Integer>(); //인접 리스트 초기화
		}		
		
		for(int i = 1; i < m+1; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			A[s].add(e);
			A[e].add(s); //인접 그래프 추가 
		}
		
		for(int i = 1; i < n+1; i++) {
			Collections.sort(A[i]);
		} //번호가 작은 것들을 먼저 방문하기 위함. 
		
		visited = new boolean[n+1];
		DFS(v);
		System.out.println();
		visited = new boolean[n+1];
		BFS(v);
		
	}
	static void DFS(int s) { //시작 노드 v
		System.out.printf(s + " ");
		if(visited[s]) return;
		visited[s] = true;
		
		for(int a : A[s]) {
			if(!visited[a]) 
				DFS(a);
		}
	}
	
	static void BFS(int s) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(s);
		visited[s] = true;
		
		
		while(!q.isEmpty()) {
			int current_node = q.poll();
			System.out.printf(current_node + " ");
			for(int a: A[current_node]) {
				if(!visited[a]) {
					visited[a] = true;
					q.add(a);
				}
			}
		}
		
	}
	
		

}