알고리즘 및 코테 복습 - DFS, BFS, 이진 탐색

⬛ 05. 탐색

• 그래프의 순회 (=탐색)
• 현재 정점 처리 후 다음 처리할 정점에 대한 순서가 필요
• 한 정점에서 시작하여 그래프의 모든 정점을 한 번씩만 방문할 것.

⬛ 05-1. 깊이 우선 탐색 | DFS

• DFS는 한 번씩만 방문해야 하므로 visited[] 방문 체크 배열 필요하며 인접 리스트로 표현

🟦 백준 11724번. 연결 요소의 개수 구하기

• DFS로 깊이 방문 하다가 복귀하는 게 한 덩어리 단위임

import java.util.ArrayList;
import java.util.Scanner;

/*11724번. 연결 요소의 개수 */
public class Main {
	static int N, M;
	static boolean[] visited;
	static ArrayList<ArrayList<Integer>> graph;
	
	//dfs
	static void dfs(int v) {
		visited[v] = true;//현재 정점 방문 처리 
		
		for(int nx : graph.get(v)) { //얘의 인접 정점들에 대하여 
			if(!visited[nx]) {
				dfs(nx);//재귀 더 깊이 방문 
			}
		}
	}
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		//초기화
		visited = new boolean[N+1];
		//공간 생성 
		graph = new ArrayList<>();
		for(int i=0; i<=N; i++) {
			graph.add(new ArrayList<Integer>());
		}
		
		for(int i=0; i<M; i++) {
			int a =kb.nextInt();
			int b = kb.nextInt();
			//양방향이므로 양쪽에 모두 저장 
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		int answer =0;
		for(int i=1; i<=N; i++) {
			if(!visited[i]) {
				dfs(i);//방문 안한 정점에 대하여 dfs 호출하면 
				answer++;//여기서 복귀하면 호출 후 복귀한 게 한 덩어리 단위임
			}
		}
		//정답 출력 
		System.out.println(answer);
	}
}

---

🟦 백준 2023번. 신기한 소수

package to_0718_1;

import java.util.Scanner;

//신기한 소수 
public class Main {
	static int N;//자릿수 == 깊이 
	static boolean visited[];//방문 체크용 배열 
	
	//소수 판별용 함수 
	static boolean isSosu(int a) {
		for(int i=2; i<=a/2; i++) {
			if(a % i == 0) {
				return false; 
			}
		}	
		return true;
	}
	
	//dfs
	static void dfs(int num, int lv) {
		if(lv == N) {//주어진 자릿수 까지 뻗은 경우 
			//완성된 4자리를 다시 소수 판별 후 
			if(isSosu(num)) {
				System.out.println(num);//출력 
			}
			return;//아니면 그냥 반환 
		}
		for(int i=1; i<10; i++) {
			if(i % 2==0)  {//짝수는 그냥 건너뛰고 
				continue;
			}
			if((isSosu(num * 10 + i))) { //추가한 숫자를 현재 숫자 뒤에 이어붙여서 소수 판별 
				dfs(num * 10 + i, lv+1); //더 깊이 탐색 
			}
		}
	}
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		
		dfs(2, 1);//2로 시작하는 값 - 1의 자리
		dfs(3, 1);
		dfs(5, 1);
		dfs(7, 1);
	}
}

---

⬛ 05-2. 너비 우선 탐색 | BFS

- BFS는 Queue를 사용하여 가까운 인접 정점들 우선 탐색하는 특징이 존재

🟦 백준 1260번. DFS와 BFS

package to_0718_4;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*1260번. DFS, BFS */
public class Main {
	static int N, M, st;
	static boolean[] visited;
	static ArrayList<ArrayList<Integer>> graph;
	//dfs
	static void dfs(int v) {
		if(!visited[v]) {
			System.out.print(v + " ");//
		}
		visited[v] = true;
		for(int nx : graph.get(v)) {
			if(!visited[nx]) { //방문 안한 인접 정점에 대하여 
				dfs(nx);//더 깊이 탐색할 건데 
			}
		}
	}
	//bfs
	static void bfs(int v) {
		Queue<Integer> Q = new LinkedList<>();
		Q.add(v);
		visited[v] = true;
	
		while(!Q.isEmpty()) {
			int cur = Q.poll();
			System.out.print(cur + " "); //여기서 출력시킴 
			for(int nx : graph.get(cur)) {
				if(!visited[nx]) {
					Q.add(nx);
					visited[nx] = true;//방문 처리 
				}
			}
		}
	}
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		st = kb.nextInt();
		
		graph = new ArrayList<>();
		for(int i=0; i<=N; i++) {
			graph.add(new ArrayList<>());
		}
		for(int i=0; i<M; i++) {
			int a =kb.nextInt();
			int b = kb.nextInt();
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		//번호 작은 거 우선으로 방문하기 위해 각각 정점에 대한 정렬 
		for(int i=0; i<=N; i++) {
			Collections.sort(graph.get(i)); //각 정점 i에 연결된 정점들 오름차순 정렬 
		}
		
		visited = new boolean[N+1];
		dfs(st);
		System.out.println();
		//visited 갱신 
		visited = new boolean[N+1];
		bfs(st);
	}
}

---

🟦 백준 2178번. 미로찾기

• BFS로 풀어야 하는 이유는 BFS가 인접 정점을 우선 탐색하는 애이기 때문이다.
• 자연스럽게 더 가까운 정점에 먼저 방문하므로, 방문한 정점의 값에 직전 정점 + 1 처리를 반복해서 해주면 마지막 A[][] 값은 최솟값이 담겨 있게 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/*2178번. 미로 탐색 */
public class Main {
	//4방향 배열 
	static int dx[] = {0,0, 1, -1};
	static int dy[] = {1, -1, 0, 0};
	
	static int N, M;
	static boolean[][] visited; //방문 체크용 배열 
	static int[][] A;//원본 배열 
	
	//bfs
	static void bfs(int i, int j) {
		Queue<int[]> Q = new LinkedList<>();
		Q.add(new int[] {i,j});
		visited[i][j] = true;
		
		while(!Q.isEmpty()) {
			int[] cur = Q.poll();
			//4방향으로 움직일 건데 
			for(int k=0; k<4; k++) {
				int nx = cur[0] + dx[k];
				int ny = cur[1] + dy[k];
				if(nx>=0 && ny >=0 && nx<N && ny<M) {
					if(A[nx][ny] !=0 && !visited[nx][ny]) {
						visited[nx][ny] =true;
						A[nx][ny] = A[cur[0]][cur[1]] + 1;
						Q.add(new int[] {nx, ny});
					}
				}
			}
		}
	}
	
	//실행 메인 
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//데이터 입력받기 
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		A = new int[N][M];
		visited = new boolean[N][M];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			String line = st.nextToken();
			for(int j=0; j<M; j++) {
				A[i][j] = Integer.parseInt(String.valueOf(line.charAt(j)));
			}
		}
		bfs(0, 0);//시작 0,0에서 하고 		
		//최종 
		System.out.println(A[N-1][M-1]);//0부터 시작해으니 마지막 배열에 최종 최솟값 담김 
	}
}

---

⬛ 05-3. 이진 탐색 | (=이분 검색) Binary Search

• 데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘
• 대상 데이터 중앙값 vs키값 비교하여 검색 범위를 절반씩 줄인다.

정렬된 자료의 중앙값 vs 키값 비교하며

1. 중앙값 < 키값 : 오른쪽 부분에 대하여 탐색
2. 중앙값 > 키값 : 왼쪽 부분에 대하여 탐색
3. 중앙값 == 키값 : 탐색 종료

---

🟦 백준 1920번. 원하는 정수 찾기

import java.util.Arrays;
import java.util.Scanner;

//이분탐색 
public class Main {
	static int N, M;
	static int A[];
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);

		N = kb.nextInt();
		A = new int[N];
		
		for(int i=0; i<N; i++) {
			A[i] = kb.nextInt();
		}
		//대상 데이터들 정렬 
		Arrays.sort(A);
		
		M = kb.nextInt();
		for(int i=0; i<M; i++) {
			boolean find = false;
			int target = kb.nextInt();
			
			//이진 탐색 시작 
			int st = 0;
			int ed = A.length - 1;//범위 끝에 달고
			while(st <= ed) {
				int mid = (st+ed) /2;
				int mVal = A[mid];
				
				if(mVal < target) {
					st = mid + 1;//시작범위를 중앙+1에 두고 오르쪽 탐색 
				}else if(mVal > target) {
					ed = mid-1;//끝범위를 중앙 -1에 두고 왼쪽 탐색 
				}else if(mVal == target) {
					find=true;
					break;
				}
			}
			if(find) {
				System.out.println(1);
			}else {
				System.out.println(0);
			}
		}
	}
}