DFS

package Section7;

class Node{
    int data;
    Node lt;
    Node rt;
    public Node(int val){
        data = val;
        lt=null;
        rt=null;
    }
}


public class DFS {

    public static void dfs(Node root){
        if (root==null) return;
        else {
            //출력을어디서하냐에따라 전위 중위 후위로 나뉨
            // 전위순회
            dfs(root.lt);
            //중위순회
            System.out.println(root.data);
            dfs(root.rt);
            //후위순회
        }
    }

    public static void main(String[] args) {

        Node root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(5);
        root.rt.lt= new Node(6);
        root.rt.rt = new Node(7);
        dfs(root);

    }
}

• 깊이우선탐색
• 스택 사용

BFS

package Section7;

import java.util.LinkedList;
import java.util.Queue;

//class Node{
//    int data;
//    Node lt;
//    Node rt;
//    public Node(int val){
//        data = val;
//        lt=null;
//        rt=null;
//    }
//}


public class BFS {

    public static void bfs(Node root){
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()){
            Node out = q.poll();
            if (out.lt!=null) q.offer(out.lt);
            if (out.rt!=null) q.offer(out.rt);
            System.out.println("out = " + out.data);

        }
    }

    public static void main(String[] args) {

        Node root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(5);
        root.rt.lt= new Node(6);
        root.rt.rt = new Node(7);
        bfs(root);

    }
}

BFSwithLevel

package Section7;

import java.util.LinkedList;
import java.util.Queue;

//class Node{
//    int data;
//    Node lt;
//    Node rt;
//    public Node(int val){
//        data = val;
//        lt=null;
//        rt=null;
//    }
//}


public class BFSwithLevel {

    public static void bfs(Node root){
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        int level = 0;
        while (!q.isEmpty()){
            int length = q.size();
            for (int i=0; i<length; i++){
                Node out = q.poll();
                if (out.lt!=null) q.offer(out.lt);
                if (out.rt!=null) q.offer(out.rt);
                System.out.println(level+" : " + out.data);

            }
            level+=1;
        }
    }

    public static void main(String[] args) {

        Node root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(5);
        root.rt.lt= new Node(6);
        root.rt.rt = new Node(7);
        bfs(root);

    }
}

• 너비우선탐색
• 최단거리를 구하는 알고리즘
• 큐 사용

BFS 최단거리 찾기

package Section7;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class problem0706RE {

    static int[] check = new int[10001];
    static int[] jump = {1, -1, 5};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        int e = in.nextInt();
        check[s] = 1;
        Queue<Integer> q = new LinkedList<>();
        q.offer(s);
        int level = 0;
        while (!q.isEmpty()) {
            int length = q.size();
            for (int i = 0; i < length; i++) {
                int now = q.poll();
                for (int j : jump) {
                    int nowNext = now + j;
                    if (nowNext >= 1 && nowNext <= 10000 && check[nowNext] == 0) {
                        if (nowNext == e) {
                            System.out.println(level + 1);
                            return;
                        }
                        check[nowNext]=1;
                        q.offer(nowNext);

                    }
                }
            }
            level += 1;
        }
    }
}

• check 배열을 사용해 시간복잡도를 줄임
  • 이미 방문한 값은 방문하지 않도록 함