자바 DFS, BFS 이론, 구현, 활용

baaaaaaaaaaaaaaaaaaaaaaarkingdog.tistory.com/729

[실전 알고리즘] 0x05강 - BFS, DFS_구버전

매우 이해하기 쉽게 정리해주신..!!

 

 

BFS는 큐로 구현, DFS는 스택/ 재귀함수

 

BFS : 깊게 깊게 -> 처음 넣은 거 먼저 탐색하는 큐

DFS :  넓게 넓게 -> 마지막에 넣은 거 먼저 탐색하는 스택

//재귀적 dfs
public static void dfs(int i) {
    checked[i] = true; //먼저 방문했다고 표시
    System.out.print(i + " ");
    
    for(int j = 1; j <= n; j++) {
      if(check[i][j] == 1 && checked[j] == false) { //이어져있고 방문 안한 곳 
        dfs(j);
      }
    }
  }

//큐로 bfs 구현
public static void bfs() {
    Queue<Integer> queue = new LinkedList<Integer>(); ///큐
    queue.offer(start); //시작점도 Queue에 넣어야 함
    checked[start] = true; //방문 표시
    System.out.print(start + " ");
    
    //Queue가 빌 때까지 반복. 방문 정점은 확인, 출력 후 Queue에 넣어 순서대로 확인
    while(!queue.isEmpty()) { 
      int temp = queue.poll();
      
      for(int j = 1; j <= n; j++) {
        if(check[temp][j] == 1 && checked[j] == false) { //이어져있고 방문 안한 곳
          queue.offer(j); //큐에 넣고
          checked[j] = true; //방문 표시
          System.out.print(j + " ");
        }
      }
    }

---

dfs 이용해서 나올수 있는 값 구하기 -> jjjayyy.tistory.com/87

[프로그래머스] 알고리즘 연습 문제 : 타겟 넘버 (자바/JAVA)

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        answer = dfs(numbers, 0, 0, target);
        return answer;
    }
    int dfs(int[] numbers, int n, int sum, int target) {
        if(n == numbers.length) {
            if(sum == target) {
                return 1;
            }
            return 0;
        }
        return dfs(numbers, n + 1, sum + numbers[n], target) + dfs(numbers, n + 1, sum - numbers[n], target);
    }
}

https://cocojelly.github.io/algorithm/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%97%B0%EC%8A%B5-DFS-BFS-(1)/

[프로그래머스 - 코딩테스트 연습] 깊이/너비 우선 탐색 (DFS/BFS) (1)

---

가장 많이 나오는 문제!!!

섬/ 바다 구분하기 

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] chk = new boolean[n];
        for(int i = 0; i < n; i++) {
            if(!chk[i]) {
                dfs(computers, chk, i); //dfs 탐색 기준점 달라짐 -> 새로운 섬
                answer++; //기준점이 달라질 때마다 증가
            }
        }
        return answer;
    }
    void dfs(int[][] computers, boolean[] chk, int start) {
        chk[start] = true;
        for(int i = 0; i < computers.length; i++) {
            if(computers[start][i] == 1 && !chk[i]) {
                dfs(computers, chk, i);
            }
        }
    }
}