728x90
BFS와 DFS에 사용할 명확한 코드를 발견하여 기록하려한다.
개인적인 생각이니 참고만 해주면 좋겠다.
■ BFS의 경우, 너비 우선 탐색으로 탐색할 노드를 발견하면
해당 노드를 전부 탐색한 후 다음에 탐색할 노드를 추가로 탐색하는 선입선출(FIFO) 방식 → 큐 사용
■ DFS의 경우, 깊이 우선 탐색으로 탐색할 노드를 발견하면
해당 노드를 탐색하되 해당 노드에서 탐색할 추가 노드를 우선적으로 탐색하는 후입선출(LIFO) 방식 → 스택 사용
좀더 쉽게 예를 들자면,
그래서 BFS는 FIFO 방식으로 큐를 사용하고, DFS는 LIFO 방식으로 스택을 사용한다고 생각하면 알고리즘 코드 구현에 조금 더 쉽게 접근할 수 있다. (무조건적인 방식은 아니므로, 참고만 하길 바란다.)
BFS 코드 (FIFO 방식 - queue 사용)
더보기
내가 생각하기에 BFS의 핵심은 아무래도 visitied[next] = visitied[cur] + 1; 아닐까싶다.
현재 시점을 기준으로 해당 노드의 거리를 지정할 수 있는 부분에서 깨달음을 얻었다.
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int N = input[0], M = input[1]; // N(정점의 개수), M(간선의 개수)
// 노드 세팅
LinkedList<Integer>[] node = new LinkedList[N+1];
for (int i = 0; i <= N; i++) {
node[i] = new LinkedList<Integer>(); // 노드 번호(인덱스)대로 list 초기화
}
// 양방향으로 간선 연결하기
for (int i = 0; i < M; i++) {
int[] edge = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
node[edge[0]].add(edge[1]); // 양방향으로 사용하기 위해서
node[edge[1]].add(edge[0]); // 다음과 같이 교차로 넣어준다
}
int[] visitied = new int[N+1];
Arrays.setAll(visitied, i -> -1); // 방문한 적 없다고 -1로 표기
Queue<Integer> queue = new LinkedList<>();
queue.add(1); // 나는 노드 1부터 시작하려고
visitied[1] = 0; // 노드 1을 방문했으므로 0으로 초기화 및 거리는 0으로 초기화
// bfs 탐색
while(!queue.isEmpty()){
Integer cur = queue.poll(); // 현재 나의 시작 노드 위치
for(Integer next : node[cur]){ // 현재 나의 시작 노드 위치에 연결된 노드들을 전부 탐색
if(visitied[next] != -1) continue; // 방문 한 적 있으면, 가지 않는다.
queue.add(next); // 추가로 탐색해야 할 노드들을 뒤에 붙여준다.
visitied[next] = visitied[cur] + 1; // 현재 노드에서 거리값을 1씩 증가시키기
}
}
// 최종적으로 N노드까지의 최단거리가 구해져있다!
System.out.println("N 노드까지 최단거리 : " + visited[N]);
}
}
DFS 코드 (LIFO 방식 - stack 사용)
코드는 아직 없음
728x90