BFS vs DFS

-동작과정

1. 큐 선언(2차원 배열이라면 Point 클래스를 활용) 및 시작 포인트 큐에 추가&&방문체크
2. while(!Queue.isEmpty()) 큐가 없어질 때까지 반복
3. Queue에서 poll하여 탐색 시작
4. 방향벡터를 이용해서 for문 4방탐색

• 다음 행선지 NULL체크
• 탈출 포인트 선언 (예를 들어 목적지 좌표에 도착했다면)
• 장애물 및 가지 말아야하는 곳이라면 continue로 탈출
• 탐색할 수 있는 곳이라면 방문체크 및 큐 추가 (제약사항들에 대한 조건문 추가)

-완전탐색 방식

• Queue자료형의 선입선출 특성을 활용
• 현재 지점에서 4방향에 탐색할 수 있는 곳들을 전부 큐에 추가
• 큐에 추가할 때는 한 개의 전역변수 느낌이 아닌 new키워드로 다른 객체를 추가함으로써 재귀와 같이 별도의 데이터를 관리
• 추가된 큐에 대해 한 개씩 poll해보며 완전탐색
• DFS의 경우 재귀스택을 활용한 좌표 별 데이터 관리
• BFS는 개별 객체를 통해 좌표 별 데이터 관리 (즉, 바뀌어야할 매개변수가 있다면 객체 멤버변수를 활용)

-특성

• 최단경로를 찾기위한 알고리즘으로써 DFS에 비해 속도면에서 우위를 가짐
• 미로찾기와 같은 최우선의 특정 경로를 찾는 문제에서 BFS를 떠올릴 수 있음
• DFS의 경우 먼저 탐색한 곳 쪽으로 계속 탐색을 진행하지만 BFS의 경우 현재좌표 근처로 확산하며 탐색.
  • DFS : 4.0 → 3.0 → 2.0 → 1.0 → 0.1 → …
  • BFS : 4.0 → 3.0 → 4.1 → 2.0 → 4.2 → …

-구현

• Graph

    public class Main{
        static int N, M, V; //정점 수, 간선 수, 시작 노드
        static int[][] graph;
        static boolean[] visited;
  
        public static void main(String[] args) {
                    /*
                    이 곳에 입력 및 배열 초기화를 진행하고, 배열크기에 맞게 visited배열 선언
                    */
            bfs(V);
        }
  
        //너비 우선 탐색 (그래프로 풀 경우 간선의 존재 유무만 체크하면 됨)
        static void bfs(int idx) {
            Queue<Integer> queue = new LinkedList<Integer>(); //큐 선언
  
            queue.add(idx); //큐에 시작지점을 추가
            visited[idx] = true; //방문체크
  
            while(!queue.isEmpty()){ //큐가 빌 때까지 무한루프
                int s =queue.poll(); //현재 큐에 들어있는 맨 앞의 값을 꺼냄
                for(int i =1; i< graph.length;i++){ //그래프의 길이만큼 반복하면서
                    if(graph[s][i] == 1 && !visited[i]){ //간선이 있을 때&&방문하지 않은 경우
                        queue.add(i); //큐에 계속해서 추가
                        visited[i] = true; //방문체크
                    }
                }
            }
        }
    }

• 사방탐색

    class Point{ //좌표값을 저장하기 위한 Point 클래스
        int x;
        int y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
  
    public class Main{
        static int[] dx = new int[] {-1, 0, 1, 0}; //방향벡터
        static int[] dy = new int[] {0, 1, 0, -1}; //방향벡터
        static int N, M, V; //정점 수, 간선 수, 시작 노드
        static int[][] map;
        static boolean[][] visited;
  
        public static void main(String[] args) {
                    /*
                    이 곳에 입력 및 배열 초기화를 진행하고, 배열크기에 맞게 visited배열 선언
                    */
            bfs(0, 0); //어디서부터 탐색을 할 지
        }
  
        //너비 우선 탐색 (그래프가 아닌 단순 2차원 배열 좌표값을 활용할 때
        static void bfs(int x, int y) {
            Queue<Point> q = new LinkedList<>(); //큐 선언
  
            visited[x][y] = true; //시작지점 방문체크
            q.offer(new Point(x,y)); //큐에 시작지점 추가
  
            while(!queue.isEmpty()){ //큐가 빌 때까지 무한루프
                Point p = q.poll(); // 맨 앞의 큐를 꺼내고
                for (int i = 0; i < 4; i++) { //큐에서 꺼낸 인덱스로부터 사방탐색
                    if (p.x + dx[i] < 0 || p.x + dx[i] > N - 1 || p.y + dy[i] < 0 || p.y + dy[i] > N - 1) continue; //Null 예외 처리
                    if(특정 조건 값){
                        visited[p.x + dx[i]][p.y + dy[i]] = true; //방문 체크
                        q.offer(new Point(p.x + dx[i], p.y + dy[i])); //탐색을 위한 큐 추가
                    }
                    //4방탐색을 돌면서 해야할 조건들을 추가**
                }
            }
        }
    }

System.out.println("Hello, World!");