[자료구조/코테] DFS/BFS

Depth First Search

- 시간을 우선으로 그래프를 탐색하는 알고리즘으로 시작점부터 인접한 정점을 차례대로 방문함

- Stack(FILO) 사용 , 재귀함수 형태로 사용

 

 

 

Breadth-First Search

- Queue(FIFO) 

 

 

---

 

 

JAVA_DFS예제 

class Main {
    static String[] vowels = {"A", "E", "I", "O", "U"};
    static ArrayList<String> words;

    public static void createWord(int lev, String str){
        words.add(str);
        for (int i = 0; i < 5 ; i++){
            if(lev < 5){
                createWord(lev+1, str.concat(vowels[i]));
            }
        }
    }

    public static void main(String[] args) {
        words  = new ArrayList<String>();
        createWord(0,"");
        System.out.println(words);

    }
 }

 

 

 

 

 

(프로그래머스- 타켓넘버) 

public class Main {

    public static void main(String[] args) {

          int[] arr = new int[]{1,1,1,1,1};
          int target = 3;
          System.out.println(new Main().solution(arr, target));

    }
    public int solution(int[] numbers, int target) {
        return DFS(numbers, target, 0, 0);
    }


    public int DFS(int[] numbers, int target, int index, int num) {

        if(index == numbers.length) {
            System.out.println("종료");
            return num == target ? 1 : 0;
        } else {

            System.out.println("num + numbers[index] " + num + numbers[index]);
            System.out.println("num - numbers[index] " + num + -numbers[index]);

            return DFS(numbers, target, index + 1, num + numbers[index])
                    + DFS(numbers, target, index + 1, num - numbers[index]);
        }
    }

    public static int Function(int num) {
        if (num == 1) {
            return 1;
        } else {

            return num * Function(num - 1);
        }
    }

}

출처 - n1tjrgns.tistory.com/252

 

 

 

 

 

 

출처)

1. m.blog.naver.com/lm040466/221787478911

2.