[2025 1학기 알고리즘 스터디] 박건민 #4주차

아 하기싫어요

 

오늘은dfsbfs알고리즘에대해서알아보도록하겟습니다.

알고리즘스터디장님이노래방가자고갈구는관계로시간이없어서빠르게진행해보도록하겠습니다.

 

DFS (깊이 우선 탐색)

하나의 정점에서 시작해 갈 수 있는 곳까지 최대한 깊이 탐색한 후, 더 이상 갈 곳이 없으면 다시 되돌아가며 탐색하는 방식.
스택 자료구조를 사용하거나 재귀 함수를 통해 구현한다.
탐색 경로는 분기점을 만나면 가능한 경로 중 하나를 정해 계속 내려가며, 끝까지 가면 다시 돌아와 다른 경로를 확인한다.
그래프가 트리 형태이거나, 경로의 깊이를 우선적으로 탐색해야 할 때 사용된다.

• 방문 순서가 경로에 따라 크게 달라질 수 있다.
• 구현이 간단하고, 메모리 사용이 적다.
• 모든 노드를 탐색할 수 있지만, 최단 거리를 보장하지는 않는다.

 

BFS (너비 우선 탐색)

하나의 정점에서 시작해 인접한 모든 정점을 먼저 탐색한 후, 그 정점들의 인접한 정점들을 다시 탐색하는 방식.
큐 자료구조를 사용하여 구현한다.
탐색은 계층적으로 진행되며, 가까운 정점부터 차례로 넓게 퍼져나가듯 탐색하는 특징이 있다.
그래프에서 최단 거리를 구할 때 자주 사용된다.

• 각 단계별로 모든 인접 노드를 방문하므로, 탐색 순서가 일정하다.
• 최단 거리 문제에 적합하다.
• 구현 시 큐를 사용하기 때문에 메모리 사용이 DFS보다 많을 수 있다.

 

 

DFS와 BFS의 차이점

구분DFSBFS

탐색 방식	한 방향으로 깊게 파고듦	가까운 노드부터 넓게 탐색
자료구조	스택 (또는 재귀)	큐
구현 방식	재귀 또는 스택	큐 사용 필수
최단 거리	보장하지 않음	보장함
메모리 사용	상대적으로 적음	상대적으로 큼
사용 예시	퍼즐 탐색, 조합 문제, 백트래킹	미로 최단 거리, 레벨 탐색, 최소 횟수 문제

 

DFS와 BFS의 시간복잡도

• 둘 다 O(V + E)
  • V는 정점(Vertex)의 수, E는 간선(Edge)의 수
  • 이유는 그래프의 모든 정점과 간선을 각각 한 번씩만 탐색하기 때문

 

DFS가 유리한 상황

• 가능한 모든 경우의 수를 탐색해야 할 때 (ex. 백트래킹, 조합, 순열)
• 정점이 깊게 연결되어 있고, 탐색 경로의 조건을 세부적으로 조절해야 할 때

 

BFS가 유리한 상황

• 최단 거리, 최소 횟수 문제 (ex. 미로 문제, 레벨별 탐색)
• 그래프가 넓게 퍼져 있고, 여러 경로 중 가장 빠른 길을 찾아야 할 때

 

자이제빠르게문제를풀어보겠습니다

 

 

DFS와 BFS

import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph; // 인접 리스트로 그래프 표현
    static boolean[] visited; // 방문 여부 저장

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

        int N = sc.nextInt(); // 정점 개수
        int M = sc.nextInt(); // 간선 개수
        int V = sc.nextInt(); // 시작 정점

        // 인접 리스트 초기화
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        // 간선 정보 입력
        for (int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a].add(b);
            graph[b].add(a); // 양방향 그래프
        }

        // 인접 리스트 오름차순 정렬 (작은 번호부터 탐색)
        for (int i = 1; i <= N; i++) {
            Collections.sort(graph[i]);
        }

        // DFS 실행
        visited = new boolean[N + 1];
        dfs(V);
        System.out.println(); // 줄바꿈

        // BFS 실행
        visited = new boolean[N + 1];
        bfs(V);
        System.out.println();
    }

    // 깊이 우선 탐색 (재귀)
    public static void dfs(int v) {
        visited[v] = true;
        System.out.print(v + " "); // 방문한 정점 출력

        for (int next : graph[v]) {
            if (!visited[next]) {
                dfs(next); // 방문하지 않은 정점 재귀 호출
            }
        }
    }

    // 너비 우선 탐색 (큐 사용)
    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.add(start);

        while (!queue.isEmpty()) {
            int v = queue.poll();
            System.out.print(v + " "); // 방문한 정점 출력

            for (int next : graph[v]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.add(next); // 방문하지 않은 정점 큐에 추가
                }
            }
        }
    }
}

 

 

미로탐색

import java.util.*;

public class Main {
    static int N, M; // 행, 열
    static int[][] map; // 미로 정보
    static boolean[][] visited; // 방문 여부 저장
    static int[] dx = {-1, 1, 0, 0}; // 상하좌우 이동 방향
    static int[] dy = {0, 0, -1, 1};

    static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

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

        N = sc.nextInt();
        M = sc.nextInt();
        sc.nextLine(); // 개행 제거

        map = new int[N][M];
        visited = new boolean[N][M];

        // 미로 정보 입력
        for (int i = 0; i < N; i++) {
            String line = sc.nextLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = line.charAt(j) - '0';
            }
        }

        // BFS 실행
        System.out.println(bfs(0, 0));
    }

    // BFS를 통해 최소 칸 수 탐색
    public static int bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        visited[x][y] = true;
        queue.add(new Point(x, y));

        // 탐색 거리 기록 (map을 재활용)
        while (!queue.isEmpty()) {
            Point p = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                // 범위 밖이거나, 벽이거나, 이미 방문한 경우 skip
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;
                if (map[nx][ny] == 0 || visited[nx][ny])
                    continue;

                // 방문 처리 및 거리 누적
                visited[nx][ny] = true;
                map[nx][ny] = map[p.x][p.y] + 1; // 이전 거리 + 1
                queue.add(new Point(nx, ny));
            }
        }

        // 도착 지점의 값이 최소 칸 수
        return map[N - 1][M - 1];
    }
}

 

연결요소의개수

import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph; // 그래프를 인접 리스트로 표현
    static boolean[] visited; // 방문 여부 저장

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

        int N = sc.nextInt(); // 정점의 수
        int M = sc.nextInt(); // 간선의 수

        // 인접 리스트 초기화
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        // 간선 입력 및 양방향 연결
        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
            graph[v].add(u); // 무방향 그래프이므로 양쪽에 모두 추가
        }

        visited = new boolean[N + 1]; // 정점 방문 여부 저장 배열
        int count = 0; // 연결 요소 개수

        // 각 정점에 대해 DFS를 수행 (방문 안 한 경우만)
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                dfs(i); // DFS 또는 BFS 모두 가능
                count++; // DFS 한 번 끝날 때마다 새로운 연결 요소
            }
        }

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

    // DFS 구현
    public static void dfs(int v) {
        visited[v] = true;

        for (int next : graph[v]) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }
}

 

 

이제빠르게노래방가보겠습니다.