DFS, BFS 알고리즘

DFS

=Depth First Search

=깊이 우선 탐색

깊은 부분을 우선으로 탐색하는 알고리즘

스택 자료구조를 이용한다.

or 재귀함수를 사용한다.

 

BFS

=Breadth First Search

=넓이 우선 탐색

가까운 노드부터 우선으로 탐색하는 알고리즘이다.

큐 자료구조를 이용한다.

 

DFS와 BFS는 코딩테스트에서 빈출하는 개념이다.

그래서 두 개념을 잘 숙지해두는게 좋다.

* 개념 정리 잘해둔 블로그 : https://devuna.tistory.com/32

 

문제

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

1260번: DFS와 BFS

 

내 풀이

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

public class Main
{
    private static ArrayList<Integer>[] nodes;
	private static boolean[] visit;
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int node_num = Integer.parseInt(st.nextToken());
		int edge_num = Integer.parseInt(st.nextToken());
		int start_node = Integer.parseInt(st.nextToken());
		visit = new boolean[node_num + 1]; // 0빼니까
		nodes = new ArrayList[node_num + 1];
		Arrays.fill(visit, false);
		
		for (int i = 1; i <= node_num; i++) {
		    nodes[i] = new ArrayList<Integer>();
		}
		
		int node1 = 0, node2 = 0;
		for (int i = 0; i < edge_num; i++) {
		    st = new StringTokenizer(br.readLine());
		    node1 = Integer.parseInt(st.nextToken());
		    node2 = Integer.parseInt(st.nextToken());
		    nodes[node1].add(node2);
		    nodes[node2].add(node1);
		}
		
		// 번호 작은 노드 먼저 접근하기 위해 오름차순으로 정렬
		for (int i = 1; i <= node_num; i++) {
            Collections.sort(nodes[i]);	    
		}
		
		DFS(start_node);
		bw.write("\n");
	    visit = new boolean[node_num + 1]; // 접근 기록 다시 초기화
	    BFS(start_node);
	    bw.flush();
	    bw.close();
	    br.close();
	}
	
	public static void DFS(int start_node) throws IOException{
        visit[start_node] = true;
        bw.write(String.valueOf(start_node) + " ");
        
        for (int i : nodes[start_node]) {
            if (visit[i] == false) {
                DFS(i); // 재귀함수
            }
        }
    } 
    
    
    public static void BFS(int start_node) throws IOException {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(start_node);
        visit[start_node] = true;
        
        while (!queue.isEmpty()) {
            int current_node = queue.poll();
            bw.write(String.valueOf(current_node) + " ");
            for (int i : nodes[current_node]) {
                if (visit[i] == false) {
                    visit[i] = true;
                    queue.add(i);
                }
            }
        }
    } 
}

ArrayList 배열을 만들어서 노드 안에 그 노드와 연결된 노드 정보를 넣고, 이걸 이용해서 BFS와 DFS를 했다.

BFS는 재귀함수를 사용했고, DFS는 큐를 사용해서 연결된 노드인데 접근하지 않은 노드면 큐에 넣고 큐 안에 있는 노드들을 순서대로 빼면서 현재 노드를 출력했다.

 

tip

nodes[node1].add(node2);
nodes[node2].add(node1);

처음 BFS와 DFS를 공부할 때 이 부분이 잘 이해가 안됐는데

nodes[node1]이게 'node1'번 노드고, 이 'node1'번 노드가 포인터처럼 'node2'의 주소를 갖고 있다(가리킨다)고 생각하니까 이해가 잘됐다!