[백준 11724번, 2178번, 1920번] 탐색(Java)

DFS, BFS는 중요하니까,,⭐️
[🍀 인프런 : Do it! 알고리즘 코딩테스트 with JAVA]로 공부하고
다시 업로드하게 되었다 

나한테 DFS, BFS 문제 보내셈!ㅋㅋ

 

깊이 우선 탐색(DFS:depth-firsh-search)

그래프 완전 탐색 기법 중 하나이다.

그래프의 시작 노드에서 출발하여 탐색할 쪽 분기를 정하여 최대 깊이까지 탐색을 탐색을 마친 후

다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

 

 

🔍 특징

• 재귀 함수로 구현 ➡️ 스택 오버플로에 유의
• 스택 자료구조 이용(FILO)
• 시간 복잡도(노드 수: V, 에지 수: E) = O(V + E)
• 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬

 

💡 핵심 이론

DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로

노드 방문 여부를 체크할 배열이 필요하며,

그래프는 인접 리스트로 표현한다.

 

 

 

023. 연결 요소의 개수 구하기(백준 11724번)

 

그래프를 인접 리스트로 저장하고 방문 배열도 초기화한다.
방향이 없는 그래프이기 때문에 양쪽 방향으로 에지를 모두 저장한다.

 

임의의 시작점에서 DFS를 수행한다.
현재의 경우 1을 시작점으로 정했다.
탐색을 마친 이후 방문한 곳은 1, 2, 5가 되었다.

 

아직 방문하지 않은 노드가 있으므로 시작점을 다시 정해 탐색을 진행한다.
현재의 경우 3, 4, 6 순서로 탐색을 마쳤다.
모든 노드를 방문했으니 전체 탐색을 종료한다.

 

총 2번의 DFS가 진행되었다는 것을 알 수 있다.
즉, 연결 요소 개수는 2개이다.
만약 그래프가 모두 연결되어 있었다면 DFS는 1번 실행되었을 것이다.

 

 

 

 

📖 정답 코드

ArrayList[] : ArrayList 객체를 저장할 수 있는 배열으르 선언한다.
ArrayList<>() : ArrayList 객체를 생성한다.

---

너비 우선 탐색(BFS:breadth-first-search)

그래프 완전 탐색 기법 중 하나이다.

시작 노드에서 출발해 시작 노드를 기준으로

가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

 

 

🔍 특징

• 큐 자료구조 이용(FIFO)
• 시간 복잡도(노드 수: V, 에지 수: E) = O(V + E)
• 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로 보장

 

💡 핵심 이론

BFS도 한 번 방문한 노드를 다시 방문하면 안 되므로

노드 방문 여부를 체크할 배열이 필요하며,

그래프는 인접 리스트로 표현한다.

 

 

 

027. 미로 탐색하기(백준 2178번)

 

2차원 배열에 데이터를 저장한 다음 (1, 1)에서 BFS를 실행한다.
상, 하, 좌, 우 네 방향을 보며 인접한 칸을 본다.
인접한 칸의 숫자가 1이면서 아직 방문하지 않았다면 큐에 삽입한다.
종료 지점(N, M)에서 BFS를 종료하며 깊이를 출력한다.

 

 

 

📖 정답 코드

미로의 시작 위치가 (0, 0)이라고 가정해보면, 이때 BFS(0, 0)이 호출되면 다음과 같은 일이 일어난다.
Queue<int[]> queue = new LinkedList<>(); ➡️ 빈 큐 생성
queue.add(new int[]{0, 0});이 실행되면서 현재 위치(0, 0)이 큐에 추가된다.
이후 while 루프에서 queue.poll()로 큐의 맨 앞에 있는 위치를 꺼내 탐색하게 된다.
(0, 0)에서 갈 수 있는 인접한 위치들이 상하좌우로 계산되며, 갈 수 있는 위치가 큐에 계속 추가된다.

queue는 다음에 탐색할 위치를 담는 역할을 하고, 
int[] 배열을 사용해 좌표(x, y)를 저장하는 것이다.
BFS에서는 이 큐를 사용해 미로의 시작점과 목표 지점까지 최단 경로를 탐색하게 된다.

 

---

이진 탐색

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.

대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

 

🔍 특징

• 중앙값(median) 비교를 통한 대상 축소 방식
• 시간 복잡도 O(logN)

 

 

029. 원하는 정수 찾기(백준 1920번)

 

 

📖 정답 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        
        int m = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<m; i++) {
            int target = sc.nextInt();
            int start = 0;
            int end = arr.length - 1;
            boolean find = false;
            while(start <= end) {
                int mid = (start + end) / 2;
                int midValue = arr[mid];
                
                if(target > midValue) {
                    start = mid + 1;
                } else if (target < midValue) {
                    end = mid - 1;
                } else {
                    find = true;
                    break;
                }
            }
            if(find) sb.append("1\n");
            else sb.append("0\n");
        }
        System.out.println(sb.toString());
    }
}