[Do it] 알코테 자바 8일차

_06-1 깊이 우선 탐색 (DFS)

깊이 우선 탐색(DFS, Depth-First Search)은 그래프 완전 탐색 기법 중 하나로, 그래프의 모든 노드를 탐색할 때 사용된다.

DFS는 한 방향으로 가능한 최대 깊이까지 탐색을 진행한 후, 더 이상 갈 곳이 없으면 이전 분기점으로 돌아가 다른 분기를 탐색하는 방식으로 동작한다.

---

1. DFS 동작 원리

1. 그래프의 시작 노드에서 출발한다.
2. 현재 노드에서 방문하지 않은 인접 노드를 선택하여 깊이 방향으로 탐색을 진행한다.
3. 더 이상 방문할 노드가 없으면 재귀적으로 이전 노드로 돌아가 다른 인접 노드를 탐색한다.
4. 모든 노드를 방문할 때까지 반복한다.

---

2. DFS 구현 특징

• DFS는 재귀 함수를 주로 사용하여 구현한다.
  • 재귀 사용 시 스택 오버플로우에 주의해야 한다.
• 스택 자료 구조(FILO)를 사용하여 구현할 수도 있다.
• 한 번 방문한 노드는 다시 방문하면 안 되므로, 방문 여부를 체크하는 배열이 필요하다.
• 그래프는 일반적으로 인접 리스트로 표현한다.

---

3. DFS 예시

• 그래프

1 - 2
|   |
3 - 4

• DFS 시작: 노드 1

1 → 2 → 4 → 3

방문 순서는 탐색 방향과 그래프 구조에 따라 달라질 수 있다.

---

4. DFS 특징

• 완전 탐색: 그래프의 모든 노드를 방문
• 재귀/스택 기반 구현 가능
• 경로 탐색, 사이클 확인, 연결 요소 계산 등에 활용
• 메모리 사용량: O(N) (방문 배열 및 재귀 스택)

---

5. DFS 주의 사항

• 깊이가 매우 깊은 그래프에서는 재귀 호출로 인해 스택 오버플로우 발생 가능
• 이미 방문한 노드를 체크하지 않으면 무한 반복이 발생

---

6. 한줄 정리

DFS는 한 방향으로 깊게 탐색을 진행하고, 더 이상 갈 곳이 없으면 이전 분기로 돌아가 다른 경로를 탐색하는 그래프 탐색 알고리즘이다.

 

__[023] 연결 요소의 개수 구하기

백준 온라인 져지 11724번 https://www.acmicpc.net/problem/11724

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

public class Main {
    static ArrayList<Integer>[] graph; // 인접 리스트로 그래프 저장
    static boolean[] visited;          // 방문 체크 배열

    // DFS 탐색 함수
    static void dfs(int v) {
        visited[v] = true;            // 현재 노드 방문 처리
        for(int u : graph[v])         // 연결된 노드 탐색
            if(!visited[u]) dfs(u);   // 방문하지 않았으면 재귀 호출
    }

    public static void main(String[] args) throws Exception {
        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()); // 간선 수

        graph = new ArrayList[n+1];   // 1번부터 n번까지 사용
        for(int i=1;i<=n;i++) graph[i] = new ArrayList<>();
        visited = new boolean[n+1];    // 방문 체크 초기화

        // 간선 정보 입력
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph[u].add(v);          // 양방향 그래프
            graph[v].add(u);
        }

        int count = 0;                // 연결 요소 개수
        for(int i=1;i<=n;i++)
            if(!visited[i]) {         // 방문하지 않은 노드 발견
                dfs(i);               // DFS로 연결된 모든 노드 방문
                count++;              // 연결 요소 하나 추가
            }

        System.out.println(count);    // 결과 출력
    }
}

__[024] 신기한 소수 찾기

백준 온라인 져지 2023번 https://www.acmicpc.net/problem/2023

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());
        int[] first = {2, 3, 5, 7}; // 1자리 소수로 시작

        for (int num : first) dfs(num, 1);
    }

    // DFS: num은 현재 수, len은 자리수
    static void dfs(int num, int len) {
        if (len == N) { // N자리면 출력
            System.out.println(num);
            return;
        }

        // 다음 자리에 올 수 있는 숫자 후보 (1~9)
        for (int i = 1; i < 10; i += 2) { // 짝수는 소수 불가능
            int next = num * 10 + i;
            if (isPrime(next)) dfs(next, len + 1);
        }
    }

    // 소수 판정
    static boolean isPrime(int x) {
        if (x < 2) return false;
        for (int i = 2; i * i <= x; i++)
            if (x % i == 0) return false;
        return true;
    }
}

__[025] 친구 관계 파악하기

백준 온라인 져지 13023번 https://www.acmicpc.net/problem/13023

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

public class Main {
    static int N, M;
    static ArrayList<Integer>[] adj;
    static boolean found = false;
    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()); // 친구 관계 수

        // 인접 리스트 초기화
        adj = new ArrayList[N];
        for (int i = 0; i < N; i++) adj[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());
            adj[a].add(b);
            adj[b].add(a);
        }

        // 각 사람을 시작점으로 DFS 수행
        for (int i = 0; i < N; i++) {
            visited = new boolean[N]; // 방문 배열 초기화
            dfs(i, 1); // 현재 노드, 현재 길이
            if (found) break; // 길이 5 경로 찾으면 종료
        }

        System.out.println(found ? 1 : 0);
    }

    static void dfs(int cur, int depth) {
        if (found) return; // 이미 찾으면 더 이상 탐색 안함
        if (depth == 5) { // 길이 5(A-B-C-D-E) 도달
            found = true;
            return;
        }

        visited[cur] = true; // 현재 노드 방문 처리
        for (int next : adj[cur]) {
            if (!visited[next]) { // 아직 방문하지 않은 친구만 탐색
                dfs(next, depth + 1); // 깊이 증가하며 DFS 재귀 호출
            }
        }
        visited[cur] = false; // 다른 경로 탐색 위해 방문 해제 (백트래킹)
    }
}

_06-2 백트래킹

백트래킹(Backtracking)은 문제를 해결하기 위한 탐색 기법으로, 모든 가능한 경로를 탐색하면서 조건에 맞는 해를 찾는 알고리즘이다.

탐색 도중 선택한 경로가 유효하지 않거나 조건을 만족하지 못하면, 이전 단계로 되돌아가 다른 경로를 시도하는 방식으로 동작한다.

DFS와 구조가 매우 유사하지만, 가지치기(Pruning)를 통해 불필요한 탐색을 제거할 수 있다는 점이 특징이다.

---

1. 백트래킹 동작 원리

1. 현재 단계에서 가능한 모든 선택을 시도한다.
2. 선택한 경로가 유효한지 확인한다.
3. 유효하지 않으면 이전 단계로 돌아가 다른 선택을 시도한다.
4. 유효하면 다음 단계로 진행하며 재귀적으로 탐색을 이어간다.
5. 모든 조건을 만족하는 해를 찾거나 모든 경로를 탐색할 때까지 반복한다.

---

2. 백트래킹 구현 특징

• 재귀 함수로 구현하는 경우가 많다.
• DFS와 구조가 비슷하며, 한 방향으로 깊이 탐색 후 되돌아가기를 반복한다.
• 가지치기를 통해 유효하지 않은 경로를 조기에 배제하여 성능을 향상시킬 수 있다.
• 완전 탐색 대비 효율적이며, 특정 조건을 만족하는 해를 빠르게 찾을 수 있다.

---

3. 백트래킹 예시

• 예: 1~3까지 숫자로 만들 수 있는 순열 생성

1. 선택 순서: 1 → 2 → 3
2. 조건 불충족 시: 이전 단계로 돌아가 다른 숫자 선택
3. 모든 순열 탐색 완료: 123, 132, 213, 231, 312, 321

---

4. 백트래킹 특징

• 모든 경로 탐색 가능
• DFS와 유사한 재귀적 탐색 구조
• 조건 불충분 시 조기 종료 가능
• 순열, 조합, N-Queen, 미로 찾기 등 다양한 문제에 활용

---

5. 백트래킹 주의 사항

• 탐색 범위가 큰 문제에서는 시간 복잡도가 높아질 수 있음
• 가지치기를 잘 설계하지 않으면 불필요한 경로까지 탐색

---

6. 한줄 정리

백트래킹은 모든 경로를 탐색하면서 조건을 만족하지 못하면 이전 단계로 되돌아가 다른 경로를 시도하고, 가지치기를 통해 효율적으로 해를 찾는 탐색 알고리즘이다.

__[026] N과 M

백준 온라인 져지 15649번 https://www.acmicpc.net/problem/15649

import java.util.*;

public class Main {
    static int N, M;
    static int[] sequence;      // 현재 수열을 저장
    static boolean[] used;      // 사용된 숫자를 체크

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        sequence = new int[M];   // 길이가 M인 수열
        used = new boolean[N+1]; // 1~N 숫자 사용 여부 체크

        dfs(0); // 0번째 자리부터 시작
    }

    static void dfs(int depth) {
        // 기저 조건: 수열이 M개가 되면 출력 후 종료
        if(depth == M) {
            for(int i = 0; i < M; i++) {
                System.out.print(sequence[i] + " ");
            }
            System.out.println();
            return;
        }

        // 1부터 N까지 숫자를 선택
        for(int i = 1; i <= N; i++) {
            if(!used[i]) {           // 아직 선택되지 않은 숫자라면
                sequence[depth] = i; // 수열에 추가
                used[i] = true;      // 사용 체크
                dfs(depth + 1);      // 다음 자리로 이동
                used[i] = false;     // 백트래킹: 다음 반복 위해 사용 해제
            }
        }
    }
}

__[027] N-Queen 배치하기

백준 온라인 져지 9663번 https://www.acmicpc.net/problem/9663

import java.util.*;

public class Main {
    static int N;
    static int[] pos; // 각 행(row)에 위치한 퀸의 열(column) 정보를 저장
    static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        pos = new int[N];

        solve(0); // 0번째 행부터 시작
        System.out.println(count);
    }

    // row번째 행에 퀸을 놓는 시도를 하는 함수
    static void solve(int row) {
        if (row == N) { // N행까지 다 채웠다면, 하나의 경우 완성
            count++;
            return;
        }

        for (int col = 0; col < N; col++) {
            pos[row] = col; // row행에 col열에 퀸 놓기 시도

            if (isPossible(row)) { // 이전에 놓은 퀸과 충돌 체크
                solve(row + 1); // 가능하면 다음 행으로
            }
            // 불가능하면 다른 열(col)로 이동하여 다시 시도
        }
    }

    // 현재 row행에 놓은 퀸이 기존 퀸들과 충돌하는지 체크
    static boolean isPossible(int row) {
        for (int i = 0; i < row; i++) {
            // 같은 열에 있는지 또는 대각선에 있는지 확인
            if (pos[i] == pos[row] || Math.abs(pos[i] - pos[row]) == row - i) {
                return false; // 충돌 발생
            }
        }
        return true; // 충돌 없음
    }
}

__[028] 색종이 붙이기

백준 온라인 져지 17136번 https://www.acmicpc.net/problem/17136

import java.util.*;

public class Main {
    static int[][] paper = new int[10][10]; // 입력 종이
    static int[] remain = {0, 5, 5, 5, 5, 5}; // 남은 색종이 수 (1~5 크기)
    static int answer = Integer.MAX_VALUE; // 최소 색종이 수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                paper[i][j] = sc.nextInt();
            }
        }

        dfs(0, 0, 0); // (0,0)부터 시작, 현재 사용한 색종이 수 0
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }

    static void dfs(int row, int col, int count) {
        // 현재 사용한 색종이 수가 이미 최소값보다 크면 더 볼 필요 없음
        if (count >= answer) return;

        // 종이 끝까지 갔으면 최소값 갱신
        if (row >= 10) {
            answer = Math.min(answer, count);
            return;
        }

        // 다음 칸으로 이동
        if (col >= 10) {
            dfs(row + 1, 0, count);
            return;
        }

        // 현재 칸이 0이면 다음 칸으로
        if (paper[row][col] == 0) {
            dfs(row, col + 1, count);
            return;
        }

        // 현재 칸이 1이면, 1~5 크기의 색종이 붙이기 시도
        for (int size = 5; size >= 1; size--) {
            if (remain[size] > 0 && canAttach(row, col, size)) {
                attach(row, col, size, 0); // 색종이 붙이기
                remain[size]--;            // 남은 색종이 감소
                dfs(row, col + 1, count + 1); // 다음 칸으로 탐색
                attach(row, col, size, 1); // 붙였던 색종이 다시 제거 (백트래킹)
                remain[size]++;
            }
        }
    }

    // size x size 크기의 색종이를 (r,c)에 붙일 수 있는지 확인
    static boolean canAttach(int r, int c, int size) {
        if (r + size > 10 || c + size > 10) return false; // 범위 벗어나면 불가
        for (int i = r; i < r + size; i++) {
            for (int j = c; j < c + size; j++) {
                if (paper[i][j] == 0) return false; // 0이 있으면 불가
            }
        }
        return true;
    }

    // 색종이 붙이기/떼기
    static void attach(int r, int c, int size, int value) {
        for (int i = r; i < r + size; i++) {
            for (int j = c; j < c + size; j++) {
                paper[i][j] = value;
            }
        }
    }
}