[2025 1학기 알고리즘 스터디] 남윤찬 #4주차

이번 주차는 DFS, BFS 문제였습니다.

 

DFS와 BFS

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    public static int n;
    public static int m;
    public static int v;

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

        n = scanner.nextInt();
        m = scanner.nextInt();
        v = scanner.nextInt();
        int[][] graph = new int[n+1][n+1];

        for (int i = 1; i <= m; i++) {
            int e1 = scanner.nextInt();
            int e2 = scanner.nextInt();

            graph[e1][e2] = graph[e2][e1] = 1;
        }

        dfs(graph);
        bfs(graph);
    }

    public static void dfs(int[][] dGraph) {
        int[] isVisited = new int[n+1];
        Deque<Integer> deque = new LinkedList<>();
        deque.addLast(v);
        StringBuilder sb = new StringBuilder();

        while (!deque.isEmpty()) {
            int current = deque.pollFirst();
            if (isVisited[current] == 1) continue;
            sb.append(Integer.toString(current)).append(" ");
            isVisited[current] = 1;

            for (int i = n; i >= 1; i--) {
                if (dGraph[current][i] == 1 && isVisited[i] == 0) {
                    dGraph[current][i] = dGraph[i][current] = 2;
                    deque.addFirst(i);
                }
            }
        }

        System.out.println(sb.toString());

    }

    public static void bfs(int[][] bGraph) {
        int[] isVisited = new int[n+1];
        Deque<Integer> deque = new LinkedList<>();
        deque.addLast(v);
        StringBuilder sb = new StringBuilder();

        while (!deque.isEmpty()) {
            int current = deque.pollFirst();
            if (isVisited[current] == 1) continue;
            sb.append(Integer.toString(current)).append(" ");
            isVisited[current] = 1;

            for (int i = 1; i <= n; i++) {
                if (bGraph[current][i] == 2 && isVisited[i] == 0) {
                    bGraph[current][i] = bGraph[i][current] = 1;
                    deque.addLast(i);
                }
            }
            
        }
        System.out.println(sb.toString());

    }
}

dfs는 스택, bfs는 큐를 이용한다는 개념을 가져가는 문제

---

연결 요소의 개수

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    public static int[][] graph;
    public static int n;
    public static int m;

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

        n = scanner.nextInt();
        m = scanner.nextInt();
        graph = new int[n+1][n+1];

        for (int i = 1; i <= m; i++) {
            int e1 = scanner.nextInt();
            int e2 = scanner.nextInt();

            graph[e1][e2] = graph[e2][e1] = 1;
        }

        dfs();
    }

    public static void dfs() {
        int answer = 0;
        int[] isVisited = new int[n+1];
        Deque<Integer> deque = new LinkedList<>();
        deque.addLast(1);

        for (int k = 1; k <= n; k++) {
            if (isVisited[k] == 1) {
                continue;
            } else {
                deque.addLast(k);
                while (!deque.isEmpty()) {
                    int current = deque.pollFirst();
                    if (isVisited[current] == 1) continue;
                    isVisited[current] = 1;
        
                    for (int i = n; i >= 1; i--) {
                        if (graph[current][i] == 1 && isVisited[i] == 0) {
                            graph[current][i] = graph[i][current] = 2;
                            deque.addFirst(i);
                        }
                    }
                }
                answer++;
            }
        }

        System.out.println(answer);

    }
}

탐색을 하면 되는데? 이제 존재하는 모든 연결요소를 찾아야해서 각 노드마다 방문했는지 확인하는 배열을 탐색하면서 연결요소의 개수를 센다. 탐색은 bfs, dfs 모두 상관 없지만 나는 dfs로 진행했다.

---

미로 탐색

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

public class Main {

    public static int[][] map;
    public static int[][] counting;
    public static int n;
    public static int m;

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

        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        map = new int[n][m];
        counting = new int[n][m];

        for (int i = 0 ; i < n; i++) {
            String[] ss = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(ss[j]);
            }
        }

        bfs();
    }

    public static void bfs() {
        int[][] ways = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        Deque<int[]> deque = new LinkedList<>();
        counting[0][0] = 1;
        deque.addLast(new int[] {0,0});

        while (!deque.isEmpty()) {
            int[] current = deque.pollFirst();
            for (int[] way : ways) {
                try {
                    if (map[current[0]+way[0]][current[1]+way[1]] == 1 && counting[current[0]+way[0]][current[1]+way[1]] == 0) {
                        counting[current[0]+way[0]][current[1]+way[1]] = counting[current[0]][current[1]] + 1;
                        deque.addLast(new int[] {current[0]+way[0], current[1]+way[1]});
                    }
                } catch(Exception e){}
            }
        }
        System.out.println(counting[counting.length-1][counting[1].length-1]);
    }
}

bfs로 탐색하면서, 한 칸 나아갈 때마다 +1을 해주는 방식이다. 그렇게되면 아래와 같은 counting 배열이 완성된다.