[2024 동계 모각코] 5회차 개인 목표 및 결과

일시 : 2025.02.02. 18:00 ~ 22:00

 

[5회차 목표]

- 스택, 큐, 완전탐색, DFS, BFS 개념 학습

 

[5회차 결과]

- 완전탐색, DFS, BFS의 작동 원리와 개념에 대해 학습하였습니다.

 

1. 완전탐색(Brute Force)
- 가능한 모든 경우의 수를 전부 탐색함
- 경우의 수가 많을 경우 비효율적
- 순열, 조합, 백트래킹

package 완전탐색_BFS_DFS_250130;

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

public class P2798_블랙잭 {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // N, M을 입력받아 저장
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // N개의 배열 생성에 카드 수 저장
        int[] card = new int[N];
        // StringTokenizer을 이미 생성했으므로, 다시 생성하지 않는다.
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            card[i] = Integer.parseInt(st.nextToken());
        }
        int max = 0; // max값을 저장할 변수

        for (int i = 0; i < N-2; i++) { // 첫 번째 고정 값
            for (int j = i+1; j < N-1; j++) { // 두 번째 고정 값
                for (int k = j+1; k < N; k++) { // 세 번째 고정 값
                    int cardvalue = card[i] + card[j] + card[k];
                    if (cardvalue <= M) {
                        if (max < cardvalue) {
                            max = cardvalue;
                        }
                    }
                        // 동일한 내용 | max = Math.max(max, cardvalue);

                    }
                }
        }
        bw.write(Integer.toString(max));
        bw.flush();
    }
}

 

2. DFS(Depth First Search, 깊이 우선 탐색)
- 가능한 멀리까지 탐색한 후, 다시 되돌아오는 방식

- 재귀 또는 스택을 활용하여 구현

 

3. BFS(Breadth First Search, 너비 우선 탐색)

- 갈 수 있는 모든 노드를 우선 탐색한 후, 다음 깊이의 노드들을 탐색하는 방식

- 큐(Queue)를 활용하여 구현

package 그래프이론_250130;

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

public class P1260_DFSBFS {
    static boolean[] visit;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int[][] graph;

    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());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        graph = new int[N+1][N+1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            graph[A][B] = 1;
            graph[B][A] = 1;
        }

        visit = new boolean[N+1]; // 방문처리 초기화
        visit[V] = true; // V를 방문처리
        dfs(V);
        bw.newLine();
        bw.flush();

        visit = new boolean[N+1];
        bfs(V);
        bw.flush();
    }

    static void dfs(int V)throws IOException {
        bw.write(V + " ");
        for (int i = 1;i <= N; i++) {
            if (graph[V][i] == 1 && !visit[i]) {
                visit[i] = true;
                dfs(i);
            }
        }
    }
    static void bfs(int V)throws IOException {
        Queue<Integer> Q = new LinkedList<Integer>();
        Q.offer(V);
        visit[V] = true;

        while (!Q.isEmpty()) {
            int now = Q.poll();
            bw.write(now + " ");
            for (int i = 1; i <= N; i++) {
                if (!visit[i] && graph[now][i] == 1) {
                    Q.offer(i);
                    visit[i] = true;
                }

            }
        }
    }
}

 

[인접리스트]

package 그래프이론_250130;

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

public class 인접리스트 {
    static boolean[] visit;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    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());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());
        for (int i = 0; i <= N; i++) {
            graph.add(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());

            graph.get(a).add(b);
            graph.get(b).add(a);

        }

        for (int i = 1; i <= N; i++) {
            Collections.sort(graph.get(i)); // 정령하거라
        }

        visit = new boolean[N+1]; // 방문처리 초기화
        visit[V] = true; // V를 방문처리
        dfs(V);
        bw.newLine();
        bw.flush();

        visit = new boolean[N+1];
        bfs(V);
        bw.flush();
    }

    static void dfs(int V)throws IOException {
        bw.write(V + " ");
            for (int i = 0; i < graph.get(V).size(); i++) {
                int next = graph.get(V).get(i);
                if (!visit[next]) {
                    visit[next] = true;
                    dfs(next);
            }
        }
    }
    static void bfs(int V)throws IOException {
        Queue<Integer> Q = new LinkedList<Integer>();
        Q.offer(V);
        visit[V] = true;

        while (!Q.isEmpty()) {
            int now = Q.poll();
            bw.write(now + " ");
            for (int i = 0; i < graph.get(now).size(); i++) {
                int next = graph.get(now).get(i);
                if (!visit[next]) {
                    visit[next] = true;
                    Q.offer(next);
                }
            }

        }
    }
}