[DFS/BFS/백트래킹] 참고자료, 코드

 

1) DFS / BFS

DFS 와 BFS 개념과 알고리즘 구현에 대해 깔끔하게 정리된 글이 있어 첨부한다.

 

https://covenant.tistory.com/132

DFS BFS란? 백준 문제추천

 

 

2) 백트래킹 참고자료

 

https://zoonvivor.tistory.com/105

모든 경우의 수 (백 트래킹)

 

 

 

내 코드

1) DFS

 

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        boolean[] visited = new boolean[n];
        for(int i= 0; i<n; i++){
            if(visited[i]==false){ //방문하지 않은 노드
                dfs(computers, visited, i, n);
                //System.out.println(i);
                answer++;
            }
        }
        
        return answer;
    }
    public void dfs (int[][] computers, boolean[] visited, int a, int n){
        visited[a] = true;
        for(int i= 0; i<n; i++){ // 모든 인접노드 찾기
            if(computers[a][i]==1 && visited[i] == false){
                dfs(computers, visited, i, n);
            }
        }
    }
}

 

2) 백트래킹 (모든 경우의 수 찾기)

 

class Solution {
    public void solution(int[] numbers, int target) {
        int[] arr = new int [numbers.length];
        int n = numbers.length;
        
        dfs(numbers, arr, 0,0,n,target);
    }
    
    static void dfs(int[] numbers, int[] arr, int start, int depth, int n, int target) {
        for(int i=start; i< n ; i++){
            arr[i] = 1;
            dfs(numbers, arr, i+1, depth+1, n, target);  //다음 index부터 마지막 index까지
            arr[i] = 0;   //백트래킹. 현재 index에 대한 다른 케이스 
        }
        print(arr);
    }
}

 

위 결과에서 arr 를 print 하면

1 1 1 1 0

1 1 1 0 1

1 1 1 0 0 

....

 

이런식으로 1과 0을 사용해서 나올수 있는 모든 경우의 수가 나온다.