섹션 7. DFS, BFS 기초 섹션 - (2) DFS와 BFS

섹션 7. DFS, BFS 기초 섹션 - (2) 그래프의 순회, DFS

그래프 순회

⬛ 1) 깊이 우선 순회 : DFS

• 한 정점에서 시작하여 깊이 탐색하다가 다시 직전(마지막 방문 정점)에 돌아와 [스택 사용] 깊이 탐색을 반복

⬛ 2) 너비 우선 순회 : BFS

• 시작 정점에 대한 인접 정점들 모두를 차례로 방문하고, 다시 처음 방문했던 정점으로 되돌아와 [큐 사용] 너비 우선 탐색 반복

---

◼️ 6번. 부분 집합 구하기 | DFS

문제 설명

🟦 문제 풀이

풀이 설명

🟦 코드

/**
 * 부분집합 구하기 - DFS
 * @author MYLG
 *
 */
import java.util.*;

class Main {
	static int n;
	static int[] ch;
	//DFS
	public void DFS(int L){
		if(L==n+1){
			String tmp="";
			for(int i=1; i<=n; i++){
				if(ch[i]==1) tmp+=(i+" ");
			}
			if(tmp.length()>0) System.out.println(tmp);
		}
		else{
			//처음에는 포함시키기 
			ch[L]=1; //포함 시킴
			DFS(L+1);
			//복귀 후에는 포함 안시키기  
			ch[L]=0; //포함 안시킴
			DFS(L+1);
		}
	}
	//main
	public static void main(String[] args){
		Main T = new Main();
		n=3;
		ch=new int[n+1];
		T.DFS(1);
	}	
}

---

◼️ 7번. 송아지 찾기 - BFS 풀이

문제 설명

🟦 문제 풀이

• 레벨 탐색으로 최소 몇번의 점프 안에 E 지점에 갈 수 있는지 구해야 하는 문제이다.
• BFS(S) 로 시작을 하게 되면 1번의 점프로 뻗어갈 수 있는 근방의 좌표가 {-1, +1, +5 }로 좁혀진다.
• 만약 다음 점프할 nx 좌표가 방문 전이면서 1~10000사이의 값이면 그 상태에서 더 BFS 탐색을 시도한다.
• 그런데 만약 nx 좌표가 E 가 된다면 그때의 Lv+1 값을 리턴하고 종료하도록 한다.

🟦 코드

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

/**
 * 송아지 찾기 BFS 
 * @author MYLG
 *
 */
public class Main {
	static int S, E;
	static boolean[] visited;
	static int[] dx = {-1, +1, 5};
	//BFS
	static int BFS(int S) {
		Queue<Integer> Q = new LinkedList<>();
		Q.offer(S);
		visited[S]=  true;
		
		int L = 0;
		while(!Q.isEmpty()) {
			int len = Q.size();
			
			for(int i=0; i<len; i++) {
				int cur = Q.poll();
				
				for(int k = 0; k<3; k++) {
					int nx = cur + dx[k];
					if(nx == E) {
						return L+1;
					}
					if(nx >= 1 && nx <= 10000 && !visited[nx]) {
						visited[nx]= true;
						Q.offer(nx);
					}
				}
			}
			L++;
		}
		return 0;
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		S = kb.nextInt();
		E = kb.nextInt();
		
		visited= new boolean[20];
		
		System.out.println(BFS(S));
	}	
}

---