개인공부-9

1. DFS ( Depth-First Search )

• DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

package org.example.level1;

import java.util.ArrayList;
import java.util.List;

public class DFS {
    static boolean[] visited = new boolean[9];
    static int[][] graph = {{}, {2, 3, 8}, {1, 7}, {1, 4, 5}, {3,5}, {3, 4}, {7}, {2,6,8}, {1, 7}};
    static StringBuilder sb = new StringBuilder();

    public static void dfs(int x) {

        visited[x] = true;
        sb.append(x).append(" ");
        for(int i = 0 ; i < graph[x].length;i++){
            if(!visited[graph[x][i]]){
                dfs(graph[x][i]);
            }
        }
    }

    public static void main(String[] args) {
        dfs(1);
        System.out.println(sb);
    }
}

// 출력 : 1 2 7 6 8 3 4 5 

• 인접한 노드의 인접노드를 쭉 타고 내려간다.

2. BFS ( Breadth-First Search )

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다
• BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다
• 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다
• 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다
• 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다
• 출처 : https://freedeveloper.tistory.com/273

package org.example.level1;

import java.awt.print.Pageable;
import java.util.LinkedList;
import java.util.Queue;

public class BFS {

    static boolean[] visited = new boolean[9];
    static int[][] graph = {{}, {2, 3, 8}, {1, 7}, {1, 4, 5}, {3,5}, {3, 4}, {7}, {2,6,8}, {1, 7}};
    static StringBuilder sb = new StringBuilder();

    public static void bfs(int x){
        Queue<Integer> q = new LinkedList<>();

        q.offer(x);
        visited[x] = true;

        while(!q.isEmpty()){
           int num = q.poll();
            System.out.print(num+" ");

            for(int i =0;i<graph[num].length;i++){
                if(!visited[graph[num][i]]){
                    q.offer(graph[num][i]);
                    visited[graph[num][i]] = true;
                }
            }

        }
    }

    public static void main(String[] args) {
        bfs(1);
    }
}

3. 활용

• 얼음틀에 얼음을 얼린다.
• 틀의 모양 테투리 = 1 , 얼음을 얼릴 수 있는 곳 = 0으로 주어질 때 만들어 지는 얼음의 갯수를 구해라

package org.example.level1;

import java.util.Scanner;

public class BFSIce {

    public static int n, m;
    public static int[][] graph = new int[1000][1000];

    public static boolean dfs(int x, int y){
        if (x <= -1 || x >=n || y <= -1 || y >= m) {
            return false;
        }

        if (graph[x][y] == 0) {
            // 해당 노드 방문 처리
            graph[x][y] = 1;
            // 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
            dfs(x - 1, y);
            dfs(x, y - 1);
            dfs(x + 1, y);
            dfs(x, y + 1);
            return true;
        }
        return false;
    }


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

            // N, M을 공백을 기준으로 구분하여 입력 받기
            n = sc.nextInt();
            m = sc.nextInt();
            sc.nextLine(); // 버퍼 지우기

            // 2차원 리스트의 맵 정보 입력 받기
            for (int i = 0; i < n; i++) {
                String str = sc.nextLine();
                for (int j = 0; j < m; j++) {
                    graph[i][j] = str.charAt(j) - '0';
                }
            }

            // 모든 노드(위치)에 대하여 음료수 채우기
            int result = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    // 현재 위치에서 DFS 수행
                    if (dfs(i, j)) {
                        result += 1;
                    }
                }
            }
            System.out.println(result); // 정답 출력
        }

}