[알고리즘] 탐색

DFS 깊이 우선 탐색

백준 11724번

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static ArrayList<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());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        visited = new boolean[n+1]; // 0번 인덱스는 헷갈릴 것 같아서 사용하지 않음
        A = new ArrayList[n+1];
        for (int i = 1; i < n+1; i++) {
            A[i] = new ArrayList<Integer>(); // A 인접 리스트의 각 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); // 종료점에서 시작점으로 갈 수도 있음. 양쪽 점에서 다 add 해주기
        }
        int count = 0;
        for (int i = 1; i < n+1; i++) {
            if (!visited[i]) { // 방문하지 않은 노드가 있으면,
                count++; // 연결 요소 개수 추가해주기
                DFS(i);
            }
        }
        System.out.println(count);
    }
    // DFS 구현하기
    private static void DFS(int v) {
        if(visited[v]) { // 현재 노드가 방문 노드이면,
            return; // 더이상 탐색하지 않는다.
        }
        visited[v] = true;
        // 현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행
        for(int i : A[v]) {
            if(!visited[i]) {
                DFS(i); // 재귀적 형태
            }
        }

    }
}

- DFS() 메소드를 이해하는게 좀 어려웠는데 계속 생각하니까 이해됐다. 그래도 복습이 꼭 필요할 것 같다!

---

BFS 너비 우선 탐색

백준 1260번

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

public class Main {
    static ArrayList<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());
        int N = Integer.parseInt(st.nextToken()); // 노드의 개수
        int M = Integer.parseInt(st.nextToken()); // 에지의 개수
        int V = Integer.parseInt(st.nextToken()); // 탐색을 시작할 노드의 번호 (시작점)
        A = new ArrayList[N+1];
        // 사용할 자료구조(인접 리스트) 초기화하기
        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();
    }
    public static void DFS(int Node) {
        System.out.print(Node+" "); // 현재 노드 출력하기
        visited[Node] = true; // visited 배열에 현재 노드 방문 기록하기
        for (int i : A[Node]) { // 현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행하기(재귀적 호출)
            if (!visited[i]) {
                DFS(i);
            }
        }
    }

    public static void BFS(int Node) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(Node); // 큐 자료구조에 시작 노드 삽입하기 (add 연산)
        visited[Node] = true; // visited 배열에 현재 노드 방문 기록하기

        while (!queue.isEmpty()) { // 큐가 비어있을 때까지
            int now_Node = queue.poll(); // 큐에서 노드 데이터 가져오기 (poll 연산)
            System.out.print(now_Node+" "); // 가져온 노드 출력하기
            for (int i : A[now_Node]) { // 현재 노드의 연결 노드 중 방문하지 않은 노드를 방문 배열에 기록하고 큐에 삽입하기
                if (!visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }


}

- DFS와 BFS를 기본 구현하는 문제이다. 각각의 구현과정을 더 복습하자.

---

 

이진 탐색

백준 1920번

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); // 정렬할 수 개수
        int[] A = new int[N];
        // A 배열 저장하기
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A); // 자바 기본정렬

        int M = Integer.parseInt(br.readLine()); // 탐색할 숫자의 개수
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            boolean find = false;
            int target = Integer.parseInt(st.nextToken());

            // 이진 탐색 시작
            int start = 0;
            int end = A.length - 1;
            while (start <= end) {
                int midIndex = (start + end) / 2; // 중간 인덱스
                int midValue = A[midIndex]; // 중앙값
                if (midValue > target) {
                    end = midIndex - 1; // 오른쪽을 없애버림
                } else if (midValue < target) {
                    start = midIndex + 1; // 왼쪽을 없애버림
                } else {
                    find = true;
                    break; // 찾았으니까 반목문 종료하기
                }
            }
            if (find) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
    }
}

- 이건 구조 이해하는 건 쉬웠는데 문제 이해를 약간 잘못해서 많이 헤맸던 문제다. 

- 그리고 처음에 end = midIndex - 1이 왜 오른쪽을 없애는 거지? 라고 생각했는데, 아예 끝을 중앙값의 왼쪽으로 지정함으로써 오른쪽이 사라지는구나 라고 깨닫게되었다. 신기한 프로그래밍의 세계...