[Do it! 알고리즘 코딩테스트 - 자바 편] 06. 탐색 (DFS, BFS, 백트래킹, 이진탐색)

06. 탐색

탐색: 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘. 주어진 데이터의 성질(정렬/비정렬)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요, 직접 구현해 원리를 완벽하게 이해해야 한다.
그래프를 자주 이용한다.
( c.f. [알고리즘] 완전탐색 기법 https://velog.io/@717lumos/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89-%EA%B8%B0%EB%B2%95 )
 

06-1. 깊이 우선 탐색

DFS: 그래프 완전 탐색 기법 중 하나.
- 특징: 재귀 함수로 구현, 스택 자료구조 이용
- 시간 복잡도: O(V+E)
- 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로우에 유의해야 한다.
- DFS로 풀 수 있는 대표 문제 유형: 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬
 
DFS의 핵심 이론 - 한 번 방문한 노드를 다시 방문하면 안 되므로, 노드의 방문 여부를 체크할 배열 필요. 인접 리스트로 표현.
 
1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
- DFS를 위해 필요한 초기 작업은 (1) 인접 리스트로 그래프 표현하기, (2) 방문 배열 초기화하기, (3) 시작 노드 스택에 삽입하기 (재귀 시작하기. 방문 체크.)
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
- pop을 수행해 노드 꺼내기.
- 꺼낸 노드를 탐색 순서에 기록하고, 인접 리스트의 인접 노드를 스택에 삽입하며 방문 배열을 체크.
  (1->2, 3 이라면 1을 꺼내고 2, 3을 넣을 때 2, 3의 방문여부를 T로 변경)
3. 스택 자료구조에 값이 없을 때까지 반복하기
- 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않기

---

[11724번: 연결 요소의 개수] / 실2
방향 없는 그래프가 주어졌을 때, 연결 요소(Connected Component)의 개수를 구하는 프로그램을 작성하는 문제.
입력: 정점의 개수 N, 간선의 개수 M, 간선(양 끝 점 u, v번호로서 주어짐) 
- 같은 간선은 한 번만 주어진다.
출력: 첫째 줄에 연결 요소의 개수를 출력

import java.io.*;
import java.util.*;

public class Main {
    static List<Integer>[] graph; // 그래프 나타내는 리스트 배열
    static boolean[] visited; // 방문 확인용 배열

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);

        graph = new ArrayList[n+1]; // 0번은 사용하지 않음
        for (int i=1; i<=n; i++) graph[i] = new ArrayList<>();

        for (int i=0; i<m; i++) { // 간선 m개
            String[] uv = br.readLine().split(" ");
            int u = Integer.parseInt(uv[0]);
            int v = Integer.parseInt(uv[1]);
            // graph 각각의 리스트에 원소 삽입
            graph[u].add(v);
            graph[v].add(u);
        }

        visited = new boolean[n+1]; // 방문 확인용 배열
        int count = 0; // 연결 요소의 개수 세는 변수
        for (int i=1; i<=n; i++) {
            if (!visited[i]) {
                dfs(i);
                count++;
            }
        }
        System.out.println(count);
    }
    
    // 연결되어있는 노드는 모드 방문 처리
    static void dfs(int node) {
        visited[node] = true;
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
    }
}

 
[2023번: 신기한 소수] / 골5
앞에서부터 한 자리씩 추가하며 읽었을 때 모두 소수이면 '신기한 소수'.
N이 입력되면, N자리 수 중에서 신기한 소수를 오름차순으로 정렬해 한 줄에 하나씩 출력.
처음에 에라토스테네스의 체를 사용해 풀었는데 메모리 초과가 발생했다. 크기가 1억인 배열을 만든 것이 문제였다...
 
소수 여부를 확인하기 위해 boolean 배열 대신 boolean 메소드를 이용해, i를 약수로 갖는지 확인하는 방식으로 풀어야 했다. (i는 2 이상, i*i<=num)
사실 맨 처음에 떠올렸던 방법인데 아쉽다..! 너무 큰 메모리를 잡지 않도록 주의하자.

import java.io.*;
import java.util.*;

public class Main {
    static int n;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        // 1자리 소수에서 시작
        int[] primes = {2, 3, 5, 7};
        for (int p : primes) {
            dfs(1, p);
        }
    }
    
    // curr이 소수인 경우 계속 탐색, digit이 n자리 도달 시 출력
    static void dfs(int digit, int curr) {
        if (!isPrime(curr))
            return;
        if (digit == n) {
            System.out.println(curr);
            return;
        }

        // 다음 자릿수 붙이기 (1~9)
        for (int i=1; i<=9; i++) {
            dfs(digit+1, curr*10+i);
        }
    }

    static boolean isPrime(int num) {
        if (num < 2)
            return false;
        for (int i=2; i*i<=num; i++) {
            if (num%i==0)
                return false;
        }
        return true;
    }
}

 
[13023번: ABCDE] / 골5
총 N명이 있다. A-B-C-D-E 이렇게 5명이 이어진 관계가 존재하는지, 즉 dfs 깊이가 5이상이 되는 것이 있는지 여부를 출력.
쓸데없이 사이클 형성에 대해 고민했는데...;  사이클을 생각할 필요 없었다. 
이 문제에서는 visited 방문 배열을 연결 요소 문제처럼 '한 번이라도 연결되어있는지' 확인 목적이 아니라, '이번의 쭉 긴 탐색에서 거쳤는지' 목적으로 사용해야 했다. 따라서 백트래킹 식으로 visited를 true/false 바꿔주어야 했다...!!
visited 방문 배열 사용 목적에 대해 정확하게 고민할 것!! 이건 백트래킹!!

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static boolean found = false;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        graph = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }

        visited = new boolean[N];
        for (int i = 0; i < N; i++) {
            dfs(i, 1);
            if (found) break;
        }
        System.out.println(found ? 1 : 0);
    }

    static void dfs(int node, int depth) {
        if (found) return; // 이미 찾았으면 중단
        if (depth == 5) {
            found = true;
            return;
        }

        visited[node] = true;
        for (int next : graph[node]) {
            if (!visited[next]) {
                dfs(next, depth + 1);
            }
        }
        visited[node] = false;
    }
}

---

06-2. 백트래킹

백트래킹: 문제를 해결하는 모든 경로를 탐색하는 기법. (조건에 맞는)
- 특징: 재귀 함수로 구현, 가지치기로 성능 향상(pruning-유효하지 않는 경로 조기 차단)
- 시간 복잡도: O(N^d)
- 백트래킹을 활용 가능한 대표 문제: 조합, 순열, N-Queens
 
백트래킹의 핵심 이론 - 문제를 해결하기 위해 가능한 경로를 탐색하면서, 조건을 만족하지 않는 경로를 가지치기해 탐색 범위를 줄임. 재귀로 구현. (바로 이전 단계로 되돌아가 다른 경로를 시도)
 
1. 가능한 선택지 탐색하기: 현재 상태에서 가능한 모든 선택지를 탐색
2. 유효성 검사 및 가지치기: 각 선택지가 문제의 조건을 만족하는지 검사. 만약 조건을 만족하지 않으면, 해당 경로는 더이상 탐색하지 않고 즉시 이전 단계로 되돌아감.
3. 해답 도출하기: 조건을 만족하는 해답을 찾으면 이를 기록하고, 필요에 따라 다른 경로도 계속 탐색.

---

[15649번: N과 M] / 실3
자연수 N과 M이 주어졌을 때, "1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열"(길이가 M)을 모두 구하기
아래처럼 풀었는데, 사용한 값인지 확인하는 코드와 현재 수열의 값을 보관하는 코드를 어느 줄에 써야 할지 약간 헷갈렸다...
이건 매 회차 사용여부가 달라지는 백트래킹 문제! if문 안에서 재귀함수 진입지점 주위로 t/f 감싸자!

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static boolean[] visited;
    static int[] nums;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        visited = new boolean[n+1]; // n번이 사용되었는지를 확인 (1~n)
        nums = new int[m];
        for(int i=1; i<=n; i++) {
            dfs(i, 0);
        }
    }

    static void dfs(int curr, int idx) {
        if(visited[curr]) {
            return;
        }
        visited[curr] = true;
        nums[idx]=curr;
        if(idx==m-1){
            for(int i=0; i<m; i++) {
                System.out.print(nums[i]+" ");
            }
            System.out.println();
        } else {
            for(int i=1; i<=n; i++){
                dfs(i, idx+1);
            }
        }
        visited[curr] = false;
    }
}

 
이 풀이가 더 직관적인 것 같다.
이건 매 회차 사용여부가 달라지는 백트래킹 문제! 사용되지 않았음을 확인한 if문 내에서, 재귀함수 호출지점 위아래로 check t/f 업데이트 코드를 두어서 감싸자!

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static int[] num;
    static boolean[] check;

    static void backtracking(int cnt) {
        if (cnt == m) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < m; i++) {
                sb.append(num[i]).append(' ');
            }
            System.out.println(sb);
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!check[i]) {
                num[cnt] = i;
                check[i] = true;
                backtracking(cnt + 1);
                check[i] = false;
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        num = new int[m];
        check = new boolean[n + 1];

        backtracking(0);
    }
}

 
[N-Queen 배치하기] / 골4
https://www.acmicpc.net/problem/9663
 
[17136번: 색종이 붙이기] / 골2
https://www.acmicpc.net/problem/17136

---

06-3. BFS

BFS: 그래프 완전 탐색 기법 중 하나. 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘.
- 특징: FIFO 탐색, Queue 자료구조 이용
- 시간 복잡도: O(V+E)
 
BFS는 FIFO 방식으로 탐색하므로 큐를 이용해 구현한다.
BFS는 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로, 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.
 
BFS의 핵심 이론:
1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
3. 큐 자료구조에 값이 없을 때까지 반복하기

---

[1260번: DFS와 BFS] / 실2
DFS와 BFS를 구현하는 문제. 이 형태 완전히 암기하기!!

import java.io.*;
import java.util.*;

public class Main
{
    static int n, m, v;
    static List<Integer>[] A; // 그래프
    static boolean[] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 정점 수
        m = Integer.parseInt(st.nextToken()); // 간선 수
        v = Integer.parseInt(st.nextToken()); // 탐색 시작 정점 수
        
        A = new ArrayList[n+1]; // n+1 크기의 배열 (A[0]은 사용하지 않음)
        for(int i=1; i<=n; i++){
            A[i] = new ArrayList<>();
        }
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            // 양방향
            A[s].add(e);
            A[e].add(s);
        }
        
        // 번호가 작은 것부터 먼저 방문하기 위해 정렬
        for(int i=1; i<=n; i++){
            Collections.sort(A[i]);
        }
        
        visited = new boolean[n+1];
        dfs(v);
        System.out.println();
        
        visited = new boolean[n+1];
        bfs(v);
        System.out.println();
	}
	
	//for문+재귀
	static void dfs(int node){
	    System.out.print(node+" ");
	    visited[node]=true;
	    for(int i : A[node]){
	        if(!visited[i])
	            dfs(i);
	    }
	}
	// while문+for문+큐
	static void bfs(int node){
	    Queue<Integer> q = new LinkedList<>();
	    q.add(node);
	    visited[node]=true;
	    
	    while(!q.isEmpty()){
	        int now = q.poll();
	        System.out.print(now+" ");
	        for(int i : A[now]) {
	            if(!visited[i]){
	                visited[i]=true;
	                q.add(i);
	            }
	        }
	    }
	}
}

[2176번: 합리적인 이동경로] / 실1
https://www.acmicpc.net/problem/2176
 
[1167번: 트리의 지름] / 실1
https://www.acmicpc.net/problem/1167
 

---

06-4. 이진 탐색

이진 탐색: 데이터가 '정렬'되어 있는 상태에서 '원하는 값'을 찾아내기 위해 사용하는 알고리즘.
대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.
- 기능: 타깃 데이터 탐색
- 특징: 중앙값 비교를 이용한 대상 축소 방식
- 시간 복잡도: O(logN)
 
이진 탐색의 핵심 이론: 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복. (내림차순이라면 조건을 반대로 하여 과정을 반복)
1. 현재 데이터셋의 중앙값을 선택.
2. 중앙값 > 타깃 데이터 일 때 중앙값 기준으로 왼쪽 데이터셋을 선택.
3. 중앙값 < 타깃 데이터 일 때 중앙값 기준으로 오른쪽 데이터셋을 선택.
4. 과정 1~3을 반복하다가 중앙값==타깃 데이터일 때 탐색을 종료.
 
[1920번: 수 찾기] / 실4
https://www.acmicpc.net/problem/1920
 
[2343번: 기타 레슨] / 골5
강의 순서를 유지하면서 M개의 블루레이에 모든 강의를 나누되, 블루레이 용량의 최소값을 구하는 문제.
이진 탐색으로 가능한 최소 용량을 찾아야 함 => 각 블루레이 용량을 mid로 가정해 필요한 블루레이 개수를 계산!!

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static int[] a;

    static boolean can(int cap) {
        int cnt = 1, sum = 0;
        for (int x : a) {
            if (sum + x > cap) {
                cnt++;
                sum = 0;
            }
            sum += x;
        }
        return cnt <= m;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        a = new int[n];
        st = new StringTokenizer(br.readLine());

        int l = 0, r = 0;
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
            l = Math.max(l, a[i]);
            r += a[i];
        }

        int ans = r;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (can(mid)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        System.out.println(ans);
    }
}

 
[1300번: K번째 수]
https://www.acmicpc.net/problem/1300