[항해99 취업리부트 TIL] 3주차 5일

스케쥴/스터디

[항해99 취업리부트 TIL] 3주차 5일

hyeseong-dev 2024. 6. 10. 08:41

오늘 진행된 강의에서 학습한 내용은 무엇인가요?

백준: 알고리즘 수업 - 깊이우선탐색1

https://www.acmicpc.net/problem/24479

깊이 우선 탐색(DFS)을 사용하여 그래프의 각 정점을 방문하는 순서를 계산하는 프로그램입니다. 그래프는 인접 리스트를 사용하여 구현되었고, 시작 정점에서부터 DFS를 수행하여 각 정점의 방문 순서를 기록합니다. 프로그램의 주요 구성 요소와 동작 방식은 다음과 같습니다:

주요 구성 요소

입력 처리 및 초기화
- 정점의 수 N, 간선의 수 M, 시작 정점 R을 입력 받습니다.
- 인접 리스트 graph, 방문 여부를 저장할 배열 visited, 방문 순서를 저장할 배열 order를 초기화합니다.
그래프 구성
- 간선 정보를 입력 받아 무방향 그래프로 만듭니다.
- 각 정점의 인접 리스트를 오름차순으로 정렬합니다.
DFS 수행
- 시작 정점 R에서부터 DFS를 수행합니다.
- DFS 수행 중 각 정점을 방문하면서 방문 순서를 기록합니다.
결과 출력
- 각 정점의 방문 순서를 출력합니다.

시간 복잡도

그래프 초기화 및 간선 입력: O(N + M)
- 정점 초기화: O(N)
- 간선 입력: O(M)
인접 리스트 정렬: O(N * log N)
DFS 탐색: O(N + M)

전체 시간 복잡도는 O(N log N + M)입니다.

코드 요약

입력 받기
- BufferedReader와 StringTokenizer를 사용하여 정점의 수, 간선의 수, 시작 정점을 입력 받습니다.
그래프 초기화
- 인접 리스트 graph를 초기화합니다.
- visited와 order 배열을 초기화합니다.
간선 입력 및 그래프 구성
- 각 간선을 입력 받아 그래프를 구성합니다.
- 인접 리스트를 오름차순으로 정렬합니다.
DFS 호출
- 시작 정점에서 DFS를 호출하여 방문 순서를 기록합니다.
결과 출력
- 각 정점의 방문 순서를 출력합니다.

DFS 메소드

dfs(int node):
- 현재 노드를 방문 표시하고 방문 순서를 기록합니다.
- 인접 정점들을 탐색하여 방문하지 않은 정점에 대해 재귀적으로 DFS를 호출합니다.

전체 코드

package 깊이우선탬색1;

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

    static int N; // 정점의 수
    static int M; // 간선의 수
    static int R; // 시작 정점
    static ArrayList<Integer>[] graph; // 그래프 인접 리스트
    static boolean[] visited; // 방문 여부를 저장할 배열
    static int[] order; // 정점의 방문 순서를 저장할 배열
    static int cnt = 1; // 방문 순서 카운터

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 버퍼에서 받은 첫 줄을 읽어 N, M, R에 할당합니다.
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        // 그래프, 방문 배열, 순서 배열 초기화
        graph = new ArrayList[N + 1];
        visited = new boolean[N + 1];
        order = new int[N + 1]; // 기본값 0으로 초기화

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

        // 무방향 그래프의 간선 끝단의 각 정점을 매핑해줍니다.
        for (int i = 1; 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);
        }

        // 각 정점의 리스트를 오름차순으로 정렬합니다.
        for (int i = 1; i <= N; i++) {
            Collections.sort(graph[i]);
        }

        // 시작 정점 R에서 DFS 호출
        dfs(R);

        // 결과 출력
        for (int i = 1; i <= N; i++) {
            bw.write(order[i] + "\n");
        }
        br.close();
        bw.close();
    }

    // 깊이 우선 탐색(DFS) 메소드
    static void dfs(int node) {
        visited[node] = true; // 현재 노드를 방문으로 표시
        order[node] = cnt++; // 방문 순서 기록
        for (int neighbor : graph[node]) { // 인접 정점 탐색
            if (!visited[neighbor]) { // 아직 방문하지 않은 정점인 경우
                dfs(neighbor); // 재귀적으로 DFS 호출
            }
        }
    }
}

백준: 알고리즘 수업 - 너비우선탐색 24444번

https://www.acmicpc.net/problem/24444

너비 우선 탐색(BFS)을 사용하여 그래프의 각 정점을 방문하는 순서를 계산하는 프로그램입니다. 그래프는 인접 리스트를 사용하여 구현되었고, 시작 정점에서부터 BFS를 수행하여 각 정점의 방문 순서를 기록합니다. 프로그램의 주요 구성 요소와 동작 방식은 다음과 같습니다:

주요 구성 요소

입력 처리 및 초기화
- 정점의 수 N, 간선의 수 M, 시작 정점 R을 입력 받습니다.
- 인접 리스트 graph, 방문 여부를 저장할 배열 visited, 방문 순서를 저장할 배열 order를 초기화합니다.
- BFS에서 사용할 큐 queue를 선언합니다.
그래프 구성
- 간선 정보를 입력 받아 무방향 그래프로 만듭니다.
- 각 정점의 인접 리스트를 오름차순으로 정렬합니다.
BFS 수행
- 시작 정점 R에서부터 BFS를 수행합니다.
- BFS 수행 중 각 정점을 방문하면서 방문 순서를 기록합니다.
결과 출력
- 각 정점의 방문 순서를 출력합니다.

시간 복잡도

그래프 초기화 및 간선 입력: O(N + M)
- 정점 초기화: O(N)
- 간선 입력: O(M)
인접 리스트 정렬: O(N * log N)
BFS 탐색: O(N + M)

전체 시간 복잡도는 O(N log N + M)입니다.

코드 요약

입력 받기
- BufferedReader와 StringTokenizer를 사용하여 정점의 수, 간선의 수, 시작 정점을 입력 받습니다.
그래프 초기화
- 인접 리스트 graph를 초기화합니다.
- visited와 order 배열을 초기화합니다.
간선 입력 및 그래프 구성
- 각 간선을 입력 받아 그래프를 구성합니다.
- 인접 리스트를 오름차순으로 정렬합니다.
BFS 호출
- 시작 정점에서 BFS를 호출하여 방문 순서를 기록합니다.
결과 출력
- 각 정점의 방문 순서를 출력합니다.

BFS 메소드

bfs(int start):
- 시작 정점을 큐에 넣고 방문 표시 및 방문 순서를 기록합니다.
- 큐가 빌 때까지 반복하며, 큐에서 정점을 꺼내고 해당 정점과 인접한 정점을 방문합니다.
- 방문하지 않은 인접 정점들을 큐에 넣고 방문 표시 및 방문 순서를 기록합니다.

전체 코드

package 너비우선탐색1;

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

public class Main {

    static int N; // 정점의 수
    static int M; // 간선의 수
    static int R; // 시작 정점
    static ArrayList<Integer>[] graph; // 그래프 인접 리스트
    static Queue<Integer> queue;
    static boolean[] visited; // 방문 여부를 저장할 배열
    static int[] order; // 정점의 방문 순서를 저장할 배열
    static int cnt = 1; // 방문 순서 카운터

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 버퍼에서 받은 첫 줄을 읽어 N, M, R에 할당합니다.
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        // 그래프, 방문 배열, 순서 배열 초기화
        graph = new ArrayList[N + 1];
        visited = new boolean[N + 1];
        order = new int[N + 1]; // 기본값 0으로 초기화

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

        // 무방향 그래프의 간선 끝단의 각 정점을 매핑해줍니다.
        for (int i = 1; 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);
        }

        // 각 정점의 리스트를 오름차순으로 정렬합니다.
        for (int i = 1; i <= N; i++) {
            Collections.sort(graph[i]);
        }

        // 시작 정점 R에서 BFS 호출
        bfs(R);

        // 결과 출력
        for (int i = 1; i <= N; i++) {
            bw.write(order[i] + "\n");
        }
        br.close();
        bw.close();
    }

    // 깊이 우선 탐색(BFS) 메소드
    static void bfs(int start) {
        queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true; // 현재 노드를 방문으로 표시
        order[start] = cnt++; // 방문 순서 기록

        while(!queue.isEmpty()) {
            int node = queue.poll(); // 가장 마지막에 넣은 값을 꺼냄

            // 현재 정점과 인접한 정점을 확인
            for (int neighbor : graph[node]) { // 인접 정점 탐색
                if (!visited[neighbor]) { // 아직 방문하지 않은 정점인 경우
                    visited[neighbor] = true; // 방문기록 하였다고 true라고 변경함
                    queue.offer(neighbor); // 큐에 삽입
                    order[neighbor] = cnt++; // 방문 순서 기록
                }
            }
        }
    }

}

백준: 2644번 촌수계산

https://www.acmicpc.net/problem/2644

촌수(촌수를 계산하는 프로그램을) 계산하기 위한 BFS(너비 우선 탐색) 알고리즘입니다. 특정 시작 노드에서 특정 도착 노드까지의 최단 거리를 계산하여 촌수를 구합니다. 코드의 주요 구성 요소와 동작 방식은 다음과 같습니다:

주요 구성 요소

입력 처리 및 초기화
- 정점의 수 V, 간선의 수 E, 시작 노드 start, 도착 노드 end를 입력 받습니다.
- 인접 리스트 graph, 거리 배열 dist를 초기화합니다.
그래프 구성
- 각 노드의 인접 리스트를 초기화합니다.
- 간선 정보를 입력 받아 무방향 그래프로 만듭니다.
BFS 탐색
- 시작 노드에서 BFS를 수행하여 각 노드까지의 최단 거리를 계산합니다.
결과 출력
- 도착 노드까지의 최단 거리를 출력합니다.

시간 복잡도

그래프 초기화 및 간선 입력: O(V + E)
- 정점 초기화: O(V)
- 간선 입력: O(E)
BFS 탐색: O(V + E)
- 각 정점을 한 번 방문하고, 모든 간선을 한 번씩 탐색

전체 시간 복잡도는 O(V + E)입니다.

코드 요약

입력 받기
- BufferedReader와 StringTokenizer를 사용하여 정점의 수, 간선의 수, 시작 노드, 도착 노드를 입력 받습니다.
그래프 초기화
- 인접 리스트 graph를 초기화합니다.
- dist 배열을 초기화합니다.
간선 입력 및 그래프 구성
- 각 간선을 입력 받아 그래프를 구성합니다.
BFS 호출
- 시작 노드에서 BFS를 호출하여 각 노드까지의 최단 거리를 계산합니다.
결과 출력
- 도착 노드까지의 최단 거리를 출력합니다.

BFS 메소드

BFS(int x):
- 시작 노드를 큐에 넣고 시작 노드의 거리를 0으로 설정합니다.
- 큐가 빌 때까지 반복하며, 큐에서 노드를 꺼내고 해당 노드와 인접한 노드를 방문합니다.
- 방문하지 않은 인접 노드를 큐에 넣고 거리를 갱신합니다.

전체 코드

package 촌수계산;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static int V, E, start, end;
    static ArrayList<Integer>[] graph;
    static int[] dist;

    public static void main(String[] args) throws IOException {
        V = Integer.parseInt(br.readLine()); // 전체 노드의 수 입력
        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken()); // 시작 노드 입력
        end = Integer.parseInt(st.nextToken()); // 도착 노드 입력
        E = Integer.parseInt(br.readLine()); // 간선의 수 입력
        dist = new int[V + 1]; // 시작 노드로부터의 거리를 저장할 배열
        graph = new ArrayList[V + 1]; // 인접 리스트로 그래프 표현

        // 각 노드의 인접 리스트 초기화
        for(int i = 1; i <= V; i++)
            graph[i] = new ArrayList<>();

        // 간선 정보 입력
        for(int i = 1; i <= E; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            graph[x].add(y); // 양방향 그래프이므로 양쪽에 모두 추가
            graph[y].add(x);
        }

        solution(); // 촌수 계산 메서드 호출
        br.close();
    }

    // 촌수 계산 메서드
    static void solution(){
        Arrays.fill(dist, -1); // 거리 배열 초기화
        BFS(start); // BFS 탐색
        System.out.println(dist[end]); // 결과 출력
    }

    // BFS 탐색 메서드
    static void BFS(int x){
        Queue<Integer> Q = new LinkedList<>(); // 큐 생성
        Q.add(x); // 시작 노드 큐에 추가
        dist[x] = 0; // 시작 노드의 거리는 0
        while(!Q.isEmpty()){ // 큐가 빌 때까지 반복
            x = Q.poll(); // 큐에서 하나의 노드를 꺼냄

            for(int y : graph[x]){ // 현재 노드와 연결된 모든 노드에 대해
                if(dist[y] != -1) continue; // 이미 방문한 노드는 무시
                Q.add(y); // 방문하지 않은 노드라면 큐에 추가
                dist[y] = dist[x] + 1; // 거리 갱신
            }
        }
    }
}

질문에 대한 설명

거리 배열을 왜 -1로 초기화하는가?
- 시작 노드로부터 각 노드까지의 거리를 저장하기 위함입니다. 처음에는 모든 노드까지의 거리를 알 수 없으므로 -1로 초기화합니다.
- 이후 BFS 탐색을 통해 각 노드에 방문하면서 거리를 계산하고, 방문한 적이 없는 노드에 대해서만 거리를 갱신합니다.
- 따라서 거리 배열의 초기값을 -1로 설정하여 방문한 적이 없는 노드와 방문한 적이 있지만 거리가 아직 계산되지 않은 노드를 구분할 수 있습니다.

백준: 7562번 나이트의 이동

https://www.acmicpc.net/problem/7562

체스판 위에서 나이트의 이동을 최소 횟수로 계산하는 알고리즘입니다. 나이트는 체스판에서 특정 위치에서 시작하여 목표 위치까지 도달해야 합니다. 이 문제를 해결하기 위해 BFS(너비 우선 탐색)를 사용합니다.

주요 구성 요소

입력 처리 및 초기화
- 체스판의 크기 I, 테스트 케이스 수 T를 입력받습니다.
- 나이트의 시작 위치 (x1, y1)와 목표 위치 (x2, y2)를 입력받습니다.
BFS 탐색
- BFS를 통해 나이트의 최소 이동 횟수를 계산합니다.
- 방문 여부를 기록하는 배열 visited와 각 위치까지의 이동 횟수를 기록하는 배열 arr를 사용합니다.

시간 복잡도

BFS 탐색의 시간 복잡도는 O(I^2)입니다. 모든 위치를 한 번씩 방문하기 때문입니다.

코드 요약

입력 받기
- BufferedReader와 StringTokenizer를 사용하여 체스판의 크기와 테스트 케이스 수를 입력받습니다.
- 각 테스트 케이스마다 나이트의 시작 위치와 목표 위치를 입력받습니다.
BFS 호출
- 나이트의 시작 위치에서 BFS를 호출하여 각 위치까지의 최소 이동 횟수를 계산합니다.
결과 출력
- 목표 위치까지의 최소 이동 횟수를 출력합니다.

BFS 메소드

bfs():
- 시작 위치를 큐에 넣고 방문 배열과 이동 횟수 배열을 초기화합니다.
- 큐가 빌 때까지 반복하며, 큐에서 노드를 꺼내고 해당 노드와 인접한 모든 유효한 위치를 탐색합니다.
- 유효한 위치에 대해 방문하지 않은 경우, 큐에 추가하고 이동 횟수를 갱신합니다.

전체 코드

package 나이트의이동;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int I;
    static int x1, x2, y1, y2;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {1, 2, 2, 1, -1, -2, -2, -1};
    static int[] dy = {2, 1, -1, -2, -2, -1, 1, 2};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());

        for (int i = 1; i <= T; i++) {
            I = Integer.parseInt(br.readLine());

            arr = new int[I][I];
            visited = new boolean[I][I];

            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());

            bfs();

            sb.append(arr[x2][y2]).append("\n");
        }
        System.out.println(sb);
    }

    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x1, y1});
        visited[x1][y1] = true;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int nx = now[0];
            int ny = now[1];

            for (int i = 0; i < 8; i++) {
                int ox = nx + dx[i];
                int oy = ny + dy[i];

                // 체스판 왼쪽 최하단(0,0)부터 우측 최상단 좌표까지(I, I)만!! 탐색하기 위함(유효한 범위)
                // 만약 범위를 벗어나면 체스판 밖 범위이므로 유효하지 않음.
                boolean isStartingPoint = (ox >= 0 && oy >= 0);
                boolean isEndingPoint = (ox < I && oy < I);
                if (isStartingPoint && isEndingPoint) {
                    if (!visited[ox][oy]) {
                        q.add(new int[]{ox, oy});
                        arr[ox][oy] = arr[nx][ny] + 1;
                        visited[ox][oy] = true;
                    }
                }
            }
        }
    }
}

코드 동작

입력 처리: 체스판의 크기, 나이트의 시작 위치와 목표 위치를 입력받습니다.
BFS 탐색: 나이트의 시작 위치에서 BFS를 수행하여 각 위치까지의 최단 거리를 계산합니다.
결과 출력: 목표 위치까지의 최단 거리를 출력합니다.

오늘 얻은 인사이트는 무엇인가요?

네 개의 알고리즘 문제는 각각 그래프 탐색과 관련된 다양한 기법을 다루고 있습니다. 이를 통해 우리는 그래프 이론의 중요한 개념들과 다양한 문제 해결 방법들을 배울 수 있습니다. 아래에 각 문제를 통해 얻을 수 있는 통찰을 정리했습니다.

1. 깊이 우선 탐색 (DFS)

문제: 깊이우선탐색1

DFS 활용: DFS는 그래프에서 한 경로를 끝까지 탐색한 후, 다시 돌아와 다른 경로를 탐색하는 방식입니다. 이는 트리의 깊이를 우선 탐색하는 것과 유사합니다.
인접 리스트 활용: 그래프를 인접 리스트로 표현하여 메모리를 효율적으로 사용합니다.
재귀 사용: DFS를 재귀적으로 구현하여 각 노드의 방문 순서를 기록합니다.
정렬: 각 노드의 인접 리스트를 정렬하여 특정 순서(오름차순)로 방문할 수 있도록 합니다.

2. 너비 우선 탐색 (BFS)

문제: 너비우선탐색1

BFS 활용: BFS는 그래프에서 시작 노드로부터 모든 인접 노드를 먼저 탐색한 후, 그 인접 노드들의 인접 노드를 탐색하는 방식입니다. 이는 트리의 너비를 우선 탐색하는 것과 유사합니다.
큐 활용: BFS를 큐를 사용하여 구현합니다. 큐는 FIFO(First In First Out) 구조로, 먼저 들어온 노드를 먼저 탐색합니다.
방문 순서 기록: 방문 순서를 기록하여 탐색 순서를 추적합니다.
정렬: 각 노드의 인접 리스트를 정렬하여 특정 순서(오름차순)로 방문할 수 있도록 합니다.

3. 촌수 계산 (BFS 활용)

문제: 촌수계산

BFS 활용: BFS를 사용하여 두 노드 간의 최단 경로를 찾습니다. 이는 두 노드 간의 관계를 계산하는 문제에서 유용합니다.
거리 배열: 시작 노드로부터 각 노드까지의 거리를 기록하여 최단 거리를 계산합니다.
양방향 그래프: 그래프를 양방향으로 처리하여 무방향 그래프에서의 탐색을 구현합니다.
초기화: 거리 배열을 -1로 초기화하여 방문 여부를 체크합니다.

4. 나이트의 이동 (BFS 활용)

문제: 나이트의이동

BFS 활용: 체스판에서 나이트의 최단 이동 횟수를 계산하기 위해 BFS를 사용합니다. 이는 2D 격자에서 최단 경로 문제를 해결하는 방법입니다.
이동 패턴: 나이트의 이동 패턴을 배열로 정의하여 각 이동을 처리합니다.
유효 범위 체크: 체스판의 유효 범위를 체크하여 유효한 위치만 탐색합니다.
거리 배열: 시작 위치로부터 각 위치까지의 이동 횟수를 기록하여 최단 경로를 계산합니다.

공통된 통찰

그래프 표현: 네 문제 모두 그래프를 인접 리스트로 표현하여 메모리 사용을 효율화하고, 그래프 탐색 문제를 해결합니다.
탐색 기법: DFS와 BFS 두 가지 탐색 기법의 차이점과 각각의 활용 사례를 통해 다양한 문제 해결 방법을 배웁니다.
시간 복잡도: 각 문제의 시간 복잡도를 분석하여 알고리즘의 효율성을 평가하는 능력을 기를 수 있습니다.
초기화 및 방문 체크: 초기화와 방문 체크를 통해 그래프 탐색에서 발생할 수 있는 무한 루프와 중복 방문을 방지합니다.
재귀와 반복: DFS의 재귀적 구현과 BFS의 반복적 구현을 통해 두 가지 접근 방식의 차이점을 이해합니다.

종합적인 인사이트

문제 해결 능력 향상: 다양한 그래프 탐색 문제를 해결하면서 문제 해결 능력이 향상됩니다.
알고리즘 선택: 문제의 성격에 따라 DFS와 BFS 중 어떤 알고리즘을 선택할지 결정하는 능력을 기를 수 있습니다.
최적화 기법: 시간 복잡도와 공간 복잡도를 고려한 최적화 기법을 학습합니다.
실제 문제 적용: 이론적인 알고리즘을 실제 문제에 적용하여 실습하고, 이를 통해 이해도를 높입니다.

저작자표시 (새창열림)