[알고리즘] BFS, DFS

BFS, DFS 탐색이란?

내가 정리하려고 했던 느낌으로 정리한 분이 계셔서 링크 첨부
https://codingnojam.tistory.com/44 (DFS) => 브루트포스,백트래킹 문제에 자주 사용
https://codingnojam.tistory.com/41 (BFS) => 주로 최단거리 문제 풀 때, 다익스트라 등등

---

백준 2606

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

class Main{
    static int computerNum;
    static int connectedCom;
    static int inffectedNum = 0;
    static int[][] graph;
    static boolean[] visited;
    
    public static void main(String args[])throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        computerNum = Integer.parseInt(br.readLine());
        connectedCom = Integer.parseInt(br.readLine());
        
        graph = new int[computerNum+1][computerNum+1];
        visited = new boolean[computerNum+1];
        int startIndex = 1; 
        
        for(int i=1; i<=connectedCom ;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            graph[n][m] = graph[m][n]= 1;
        }
        
        dfs(startIndex);
        System.out.println(inffectedNum-1);
        
    }
    
    public static void dfs(int startIndex){
        visited[startIndex]=true;
        inffectedNum++;
        
        for(int i=1; i<=computerNum ; i++){
            if(graph[startIndex][i]==1 && !visited[i]){
                dfs(i);
            }
        }
    }
}

얻어갈 점:

• main함수와 메서드에서 같이 사용하고 싶은 변수가 있다면 클래스 레벨에서 static으로 선언하여 사용하는 것도 하나의 방법
• graph, visited 변수에 +1을 해주는 이유 => 1번 인덱스가 1번 노드를 가리키면 편하니까(원래는 0번 인덱스가 가리킴)
• graph[n][m] = graph[m][n]= 1 => 1번 노드와 2번 노드가 연결되어있다는 뜻 , 1을 할당하여 표시
• 인접리스트를 사용하여 구현하는 방식으로 다시 풀어봐야겠음