DFS / BFS

DFS/BFS를 한번에 정리해 보려고 한다.

DFS/BFS로 풀기 좋은 대표적 문제 유형
1.경로 탐색(최단거리/시간)
2.네트워크 유형(연결)
3.조합 유형(모든 조합 만들기)

 

 

 

DFS (깊이 우선 탐색)

한길로 쭉 가는 유형, 재귀로 구현하는 것이 일반적!

재귀를 타고타고 가서 탈출조건에 도달하고

파라미터를 하나씩 바꿔가면서 정점을 찾는 방식

 

DFS문제 예

프로그래머스-타겟 넘버

 

class Solution {
    static int answer;
    public int solution(int[] numbers, int target) {
        answer =0;
        dfs(0,0,numbers,target);
        return answer;
    }
    static void dfs(int index, int sum, int[]numbers, int target){
        if(index==numbers.length){ //index 길이가 배열의 끝까지 오면 탈출
            if(sum==target){ //그러면서 sum이 target과 일치하면 answer++
                answer++;
            }
            return;
        }
        //index를 하나씩 늘려가며 빼거나/더하는 두가지 경우로 나누어 재귀를 돌림
        dfs(index+1, sum+numbers[index], numbers, target);
        dfs(index+1, sum-numbers[index], numbers, target);
    }
}

이 경우 실제 계산 순서는 먼저 모든 조합을 더하는 경우(ex)1+1+1+1+1) 부터 계산한다.

그 후 두번째 줄의 뺄셈 재귀로 넘어가 하나를 뺀 경우(ex)1+1+1+1-1)를 계산하고 이를 반복한다 => 한길로 쭉 가서 계산하는 DFS의 특징!

 

DFS의 장점은 한길로 쭉 가기 때문에 어디서 틀렸는지 찾기가 쉽고, 따라서 동작검증을 하기 쉽다는 것이다!

 

 

 

 

 

BFS

여러 길을 가까운 순으로 하나씩 접근

Queue나 LinkedList 사용이 일반적이다.

DFS보다 구현은 복잡하나 시간복잡도가 더 낮다.

 

 

BFS의 예 

백준 - 바이러스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Baek_2606 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); //컴퓨터의 수
        int tc = Integer.parseInt(br.readLine()); //쌍의 수

        int[][] graph = new int[N+1][N+1];
        boolean[] visited = new boolean[N + 1];
        for(int i=0; i<tc; i++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[a][b] = graph[b][a] = 1;
        }

        Queue<Integer> queue = new LinkedList();
            queue.add(1);
            visited[1] = true;
        int count = 0;

        while (!queue.isEmpty()) {
            int a = queue.poll(); //큐에서 꺼낸 수를 로 만들어줌
            count++; //count해줌

            for (int j = 0; j < graph.length; j++) {
                if (graph[a][j] == 1 && visited[j]==false) { //만약 그래프에 연결되어 있는 노드가 있고 아직 방문을 안했다면
                        visited[j] = true; //방문했다고 바꿔주고
                        queue.add(j); //큐에 그 수를 담아줌
                    }
                }
        }
        System.out.println(count - 1);
    }
}

 

큐 안에 수를 하나씩 빼면서 그와 연결된 (방문하지 않은)노드들을 큐에 차례로 넣어준 후 큐가 빌 때까지 반복한다.