DFS(깊이 우선 탐색) 최대한 깊이 내려간 후, 더 이상 갈곳 없으면 뒤로 돌아오는 방식
"깊이" 현재 노드에서 연결된 노드를 재귀적으로 따라가는 것 , 미로에서 한길로 가다가 막히면 뒤로 돌아와서 다른 길이 있다면 그 길로 가는 것
BFS(너비 우선 탐색) 가까운 노드부터 차례로 탐색하는 방식.
DFS는 스택과 비슷 , BFS는 Queue(FIFO) 방식
DFS
1. 1번에서 2,3,4로 갈 수 있음 2번 으로 이동
2. 2번에서 1,4 이동할 수 있는데 1은 왔던길이니 4로 이동
3. 4번에서는 3으로 갈 수 있음.
4. 3번에서는 이미 방문했으므로 종료
고로 1->2->4->3
BFS
1. graph 리스트에 각 정점의 연결 정보를 저장
2. 시작 정점 1
3. 1에 연결된 정점 : 2,3 -> 오름차순으로 2 먼저 탐색함
4. 2에 연결된 정점 : 4,5 -> 오름차순으로 4 탐색
5. 3에 연결된 정점 : 6
나머지 이미 탐색되어있음 1,2,3,4,5,6
bfs는 Queue 인터페이스와 LinkedList를 분리해서 사용 다양한 구현체( LinkedList, PriorityQueue, ArrayDeque 등)을 활용할 수 있음.
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.poll(); // 정상 동작: Queue 인터페이스의 메서드
LinkedList<Integer> list = new LinkedList<>();
list.addFirst(1); // LinkedList 고유의 메서드 사용 가능
list.add(2);
list.removeFirst(); // Queue의 FIFO 원칙과 맞지 않음
큐의 원칙에 위배되지 않게 , 인터페이스를 통해 동작을 방지할 수 있음
LinkedList<Integer> list = new LinkedList<>();
LinkedList를 인터페이스로 했을경우 종속적이므로 지양
BFS에서 할일을 생각
1. 값 넣어주기
2. 방문 값 true로 바꿔주기
3. queue가 안비었으면 꺼낸 후 출력
4. 현재 노드와 연결된 모드 노드를 확인하고 , 방문하지 않은 노드 방문처리하고 다시 큐에 추가시킴
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.List;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
class Main{
static int N; // 정점의 개수
static int M; // 간선의 개수
static int V; // 정점 시작 번호
static List<List<Integer>> adjList; // 근접 노드
static boolean[] visited; // 방문
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
V = Integer.parseInt(st.nextToken());
adjList = new ArrayList<>(N+1);
for(int i=0; i<=N; i++){
adjList.add(new ArrayList<>());
}
for(int i=0; i<M; i++){ // 간선 입력 받아서 넣기
st = new StringTokenizer(br.readLine()," ");
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
adjList.get(u).add(v);
adjList.get(v).add(u);
}
// 각 리스트들 작은 값 먼저 나와야 함
for(int i=1; i<=N; i++){
Collections.sort(adjList.get(i));
}
visited = new boolean[N+1]; // 방문체크
dfs(V);
System.out.println("");// 줄바꿈
visited = new boolean[N+1]; // 방문체크
bfs(V);
}
// dfs private으로
public static void dfs(int n){
visited[n] = true; // 방문했으니
System.out.print(n + " ");
for(int neighbor : adjList.get(n)){ // 방문한 노드 연결된 숫자 체크
if(!visited[neighbor]){
dfs(neighbor); // 방문 안했으면 다시 넣어서 방문
}
}
}
// bfs private으로
public static void bfs(int n){
Queue<Integer> q = new LinkedList<>();
q.add(n);
visited[n] = true; // 방문했으니 true
while(!q.isEmpty()){ // q가 비어있지 않을때 까지
int current = q.poll(); // 현재 꺼 꺼냄
System.out.print(current + " ");
for(int next : adjList.get(current)){
if(!visited[next]){
visited[next] = true;
q.add(next); // next 방문 안했으면 다시 넣음
}
}
}
}
}'Algorithm' 카테고리의 다른 글
| [백준] 브1 > 세로읽기 10798번 - JAVA (0) | 2024.10.23 |
|---|---|
| [백준] 브1 > 팰린드롬수 1259번 - JAVA (0) | 2024.10.22 |
| [백준] 브1 > 피보나치 수 2 2748번 - JAVA (2) | 2024.10.21 |
| [백준] 브1 > 2007년 1924번 - JAVA (0) | 2024.10.20 |
| [백준] 브1 > 약수 1037번 - JAVA (1) | 2024.10.19 |