그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력


첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력


첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

 

풀이


public class bojtest {
    static int N, M, V;

    static ArrayList<Integer>[] arr;

    static boolean[] visited;

    static StringBuilder sb = new StringBuilder();


    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());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        arr = new ArrayList[N+1];
        visited = new boolean[N+1];
        for (int i=1; i<=N; i++){
           arr[i] = new ArrayList<>();
        }
        for (int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[s].add(e);
            arr[e].add(s);
        }
        for (int i=1; i<=N; i++){
            Collections.sort(arr[i]);
        }
        DFS(V);
        sb.append("\n");
        visited = new boolean[N+1];
        BFS(V);
        System.out.println(sb.toString());
    }
    static void DFS(int x){
        sb.append(x).append(" ");
        visited[x] = true;
        for (int i : arr[x]){
            if (!visited[i]){
                DFS(i);
            }
        }
    }

    static void BFS(int x){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        visited[x] = true;

        while (!queue.isEmpty()){
            int i = queue.poll();
            sb.append(i).append(" ");
            for (int n : arr[i]){
                if (!visited[n]){
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

해설


BFS와 DFS를 비교하는 문제였다.

단순히 DFS와 BFS를 돌리는 문제보다도, DFS와 BFS가 어떻게 실행되는지를 이해하고 언제 사용할 것인지를 파악하는데 도움이 되는 문제이다.

하나하나 천천히 코드를 뜯어보자.

static int N, M, V;
static ArrayList<Integer>[] arr;
static boolean[] visited;
static StringBuilder sb = new StringBuilder();

처음 선언해줄 변수들은 DFS에서 했던 그대로 가로, 세로, 그리고 target number와

노드의 연결고리를 기록할 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());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        arr = new ArrayList[N+1];
        visited = new boolean[N+1];
        for (int i=1; i<=N; i++){
           arr[i] = new ArrayList<>();
        }
        for (int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[s].add(e);
            arr[e].add(s);
        }
        for (int i=1; i<=N; i++){
            Collections.sort(arr[i]);
        }
        DFS(V);
        sb.append("\n");
        visited = new boolean[N+1];
        BFS(V);
        System.out.println(sb.toString());
    }

메인 스택은 3부분으로 나눌 수 있다.

1.DFS/BFS 실행을 위해 arr과 방문 배열을 선언하고 초기화하는 것, 시작과 끝 노드를 이어주는 것

2.문제에 적힌 대로 '정점 번호가 낮은 것을 먼저 선행'하기 위해 소팅을 하는것

3.DFS를 실행하고, 방문 배열을 초기화시킨 뒤 BFS를 실행하고 출력하는 것

static void DFS(int x){
        sb.append(x).append(" ");
        visited[x] = true;
        for (int i : arr[x]){
            if (!visited[i]){
                DFS(i);
            }
        }
    }

    static void BFS(int x){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        visited[x] = true;

        while (!queue.isEmpty()){
            int i = queue.poll();
            sb.append(i).append(" ");
            for (int n : arr[i]){
                if (!visited[n]){
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

DFS와 BFS 실행이다.

DFS는 실행 번호를 적어준 뒤 방문하지 않았던 노드를 토대로 방문하는 로직이다.

BFS는 Queue를 선언하고, 큐에 노드를 넣어주는 것부터 시작된다.

다음 예를 보자.

4 5 1
1 2
1 3
1 4
2 4
3 4

<DFS 실행순서>

DFS(1)을 실행한다. arr[1]에는 2, 3이 들어있으므로 1번 방문을 체크하고 DFS(2)를 실행한다.

DFS(2)을 실행한다. arr[2]에는 4가 들어있으므로 2번 방문을 체크하고 DFS(4)를 실행한다.

DFS(4)를 실행한다. arr[4]에는 아무것도 들어있지 않으므로 4번 방문을 체크하고 스택을 종료한다.

다시 1번으로 돌아가서, 스택에 쌓여 있는 DFS(3)을 실행한다.

DFS(3)을 실행한다. arr[3]에는 4가 들어있지만 방문하였으므로 그냥 종료한다.

<BFS 실행순서>

타겟 넘버가 1일경우 1을 큐에 넣는다.

현재 큐 상태 : [1]

그리고 큐에서 다시 1을 뽑아서, 1과 연결된 노드들을 다시 큐에 넣는다. 1번 방문은 체크한다.

위의 예제에서라면 2와 3을 큐에 넣을 것이다.

큐는 FIFO 구조로 돌아가니까, 2와 3을 큐에 넣을 것이다. 2와 3번 방문은 체크한다.

현재 큐 상태 : [2 3]

빈 큐가 아니므로, poll을 하면 2번 노드가 빠진다. 2번 배열에 있는 4번 노드가 queue에 추가된다. 4번 방문은 체크한다.

현재 큐 상태 : [3 4]

빈 큐가 아니므로, poll을 하면 3번 노드가 빠진다. 3번 배열에 있는 4번 노드가 queue에 추가되어야 하나, 방문 배열에 체크되어있기 때문에 넘어간다.

현재 큐 상태 : [4]

빈 큐가 아니므로, poll을 하면 4번 노드가 빠진다. 4번 배열은 연결되어있는 노드가 없으므로 BFS를 끝낸다.

 

 

위의 예제를 기준으로, 실행순서가 DFS는 1 2 4 3이 나오고 BFS는 1 2 3 4가 나온다.

스택을 기준으로 실행하는 DFS이냐, 큐를 기준으로 실행하는 BFS이냐는 문제를 점점 풀어가며 감을 익혀가야겠지만,

한가지는 알 수 있다. BFS는 최단거리를 찾는데 유용하고, DFS는 브루트 포스같이 모든 경로를 찾는 데에 유용하다.

 

 

너비 우선 탐색

너비 우선 탐색(BFS, breadth-first search)도 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘입니다.

기능 특징 시간복잡도(노드 수 : V, 엣지 수 : E)
그래프 완전 탐색 - FIFO 탐색 - Queue 자료구조 이용 O(V+E)

너비 우선 탐색은 선입선출 방식으로 탐색하므로 큐를 이용해 구현합니다. 또한 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러개일 때 최단 경로를 보장합니다.

너비 우선 탐색의 핵심 이론

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요합니다. 그래프를 인접 리스트로 표현하는 것 역시 DFS와 동일합니다. 하지만 차이점이 있다면 탐색을 위해 스택이 아닌 큐를 사용합니다.

  • 타임라인 : 원본 그래프 -> 인접 리스트 -> 방문 배열 -> 큐 삽입

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입합니다. 이 때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않습니다. 또한 큐에서 꺼낸 노드는 탐색 순서에 기록합니다.

  • 타임라인 : 큐에서 노드를 꺼내면서 탐색 순서에 꺼낸 노드를 기록 -> 인접 리스트 -> ㄷ상 노드의 인접 노드를 큐에 삽입 -> 노드를 삽입하며 방문 배열 체크

3. 큐 자료구조에 값이 없을때까지 반복하기
큐에 노드가 없을 때까지 앞선 과정을 반복합니다. 선입선출 방식으로 탐색하므로 탐색 순서가 DFS와는 다릅니다.

풀어볼 문제

문제 026 - BFS와 DFS 프로그램(1260)

문제 027 - 미로 탐색하기(2178)

문제 028 - 트리의 지름 구하기(1167)

'알고리즘' 카테고리의 다른 글

우선순위 큐를 이용한 그리디 문제  (0) 2023.10.15
이진 탐색, 이분 탐색  (0) 2023.10.04
구간합 & 투 포인터 & 슬라이딩 윈도우  (0) 2023.09.27
탐색(1) - DFS  (0) 2023.09.11
DP  (0) 2023.09.07

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

 

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

입력


첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

 

출력


첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

 

풀이


public class Main {

    static int N, M;
    static int[][] field;

    static int[][] dp;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};

    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());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        dp = new int[N][M];
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++){
                field[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }
        //DFS
        System.out.println(DFS(0,0));
    }
    static int DFS(int x, int y){
        if (x == N-1 && y == M-1){
            return 1;
        }
        if (dp[x][y] != -1){
            return dp[x][y];
        }

        dp[x][y] = 0;
        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx <N && ny < M){
                if (field[nx][ny] < field[x][y]){
                    dp[x][y] += DFS(nx, ny);
                }
            }
        }

        return dp[x][y];
    }
}

해설


https://choincnp.tistory.com/88

 

[백준/1987] - 알파벳(JAVA)

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으

choincnp.tistory.com

알파벳 문제가 DFS+DP의 맛보기라면, 이번 내리막길 문제는 본격적으로 DFS+DP를 이용하는 문제이다.

물론 DFS만 이용해서 문제를 풀 수도 있다. 그러나 문제는 시간 초과가 발생한다.

가로와 세로가 500x500까지 주어질 수 있어서, 모든 루트를 다 거쳐갈때 5초라는 시간이 발생하지만 시간 제한은 2초이기 때문이다.

<DFS만을 이용한 풀이법>

 

public class Main {

    static int N, M, answer;
    static int[][] field;
    static boolean[][] visited;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};

    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());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        visited = new boolean[N][M];
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++){
                field[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //DFS
        DFS(0,0,field[0][0]);

        System.out.println(answer);
    }
    static void DFS(int x, int y, int number){
        if (x == N-1 && y == M-1){
            answer++;
        }
        visited[x][y] = true;
        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx <N && ny < M){
                if (!visited[nx][ny] && field[nx][ny] < number){
                    DFS(nx, ny, field[nx][ny]);
                }
            }
        }
        visited[x][y] = false;
    }
}

그럼 지금부터 DP의 Top-down 방식을 이용한 풀이를 해 보자.

static int N, M;
static int[][] field;
static int[][] dp;
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};

먼저, 가로와 세로 길이인 N, M을 선언하고, 값을 입력받을 field와 dp 배열을 선언한다.

마지막으로, 길은 상하좌우로 찾아나갈 것이므로 델타배열을 선언한다.

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());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        dp = new int[N][M];
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++){
                field[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }
        //DFS
        System.out.println(DFS(0,0));
    }

메인스택 자체는 단순하다. 적절하게 변수를 초기화시켜주고,

int배열로 dp배열을 선언하였으므로, -1로 배열을 초기화해준다.

마지막으로 DFS함수만 print해주면 된다.

static int DFS(int x, int y){
        if (x == N-1 && y == M-1){
            return 1;
        }
        if (dp[x][y] != -1){
            return dp[x][y];
        }

        dp[x][y] = 0;
        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx <N && ny < M){
                if (field[nx][ny] < field[x][y]){
                    dp[x][y] += DFS(nx, ny);
                }
            }
        }

        return dp[x][y];
    }

DFS펑션이다. 

먼저 시작지점에서 끝지점까지 가는 방법의 수 자체를 출력해야 하므로, 끝 지점에 도달하였다면(x == N-1 && y == M-1)

1을 리턴하자.

최단 경로가 dp배열에 이미 기록되어있다면 바로 dp배열의 값을 리턴해준다.

마지막으로, 도달하였을경우 dp배열에 값을 0으로 바꿔주고(DFS에서 했던 visited와 비슷한 역할)

 

델타배열을 이용한 새 좌표를 구한 후 최소값으로 이동할 경우 dp배열에 DFS값을 더해준다.

만약 [x,y]발판 이후로 [N-1, M-1]까지의 경로가 존재할 경우 1이 더해질 것이고, 아니라면 아무 행동도 일어나지 않을 것이다.

Arrays.deepToString(dp) = [[3, 2, 2, 2, 1], [1, -1, -1, 1, 1], [1, -1, -1, 1, -1], [1, 1, 1, 1, -1]]

DFS를 실행시키고 난 다음 dp배열을 찍어보면 위와 같이 나온다.

이 dp배열의 뜻은 [x,y] -> [N-1, M-1]까지 가는 최단경로가 몇개나 나올 수 있을지를 찍는 배열이다.

DP는 아직 많이 학습하지 않았으므로, 나중에 따로 포스팅하겠다.

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력


첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

 

출력


첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

풀이


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

public class Main {

    static StringTokenizer st;
    static char[][] field;
    static boolean[] visited;
    static int R, C, count, max;

    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        field = new char[R][C];
        for (int i=0; i<R; i++){
            String row = br.readLine();
            for (int j=0; j<C; j++){
                field[i][j] = row.charAt(j);
            }
        }

        //DFS
        max = 1;
        visited = new boolean[26];
        count = 1;
        DFS(0,0,count);
        System.out.println(max);
    }
    static void DFS(int x, int y, int count) {
        visited[field[x][y]-65] = true;
        max = Math.max(max, count);
        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < R && ny < C){
                if (!visited[field[nx][ny]-65]){
                    DFS(nx, ny, count+1);
                }
            }
        }
        visited[field[x][y]-65] = false;
    }
}

해설


'방문한 배열에 대해 어떻게 초기화를 적절히 해 줄 수 있을까'라는 구현이 가장 핵심인 DFS문제였다.

개인적으로 DP를 왜 사용하는 지에 대한 이유를 알 수 있는 문제라 중요하다고 생각했다.

[0,0]에서 [1,0]으로 이동할때와 [0,1]로 이동할때의 최댓값에 따라 이동하는데, visited 배열을 가만히 놔두면

기존 움직임에 대해서 다음 DFS가 체크할 수 없다.

static StringTokenizer st;
static char[][] field;
static boolean[] visited;
static int R, C, count, max;
static int[] dx = {0,0,-1,1};
static int[] dy = {1,-1,0,0};

방향을 체크해야 하니 델타배열을 생성하고, field와 visited를 만든다.

처음에는 visited와 alphabet이라는 배열을 두개 생성해서 visited와 alphabet에 대해 따로따로 체크했다.

그러나 alphabet 배열을 제거했고 이유는 다음과 같았다.

배열을 두 개 만든 이유는 방문했던 위치와 알파벳이 별개로 돌아갈거라고 생각했는데 그렇지 않았다

ㅇ예를 들어 다음 입력을 가정해보자.

2 4
CAAB
ACAB

C에서 [0,1]인 A로 이동했을 때, [1,1]인 C는 가면 안된다.

그러나 방문하지 않았던 배열이기 때문에 visited와 alphabet을 따로 만들었었는데

생각해보면 '방문했던 배열의 알파벳은 다시 밟지 않는다'의 원칙이 있기 때문에 visited가 곧 alphabet이 된다.

다만 visited배열을 알파벳 대문자와 같은 26개의 크기로 만들어주고, 밟을 때마다 알파벳에 체크를 해준다.

public class Main {

    static StringTokenizer st;
    static char[][] field;
    static boolean[] visited;
    static int R, C, count, max;

    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        field = new char[R][C];
        for (int i=0; i<R; i++){
            String row = br.readLine();
            for (int j=0; j<C; j++){
                field[i][j] = row.charAt(j);
            }
        }

        //DFS
        max = 1;
        visited = new boolean[26];
        count = 1;
        DFS(0,0,count);
        System.out.println(max);
    }

그래서 배열을 초기화하고 field에 값을 채운 뒤 DFS를 돌려준다.

    static void DFS(int x, int y, int count) {
        visited[field[x][y]-65] = true;
        max = Math.max(max, count);
        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < R && ny < C){
                if (!visited[field[nx][ny]-65]){
                    DFS(nx, ny, count+1);
                }
            }
        }
        visited[field[x][y]-65] = false;
    }

가장 중요한 DFS 함수이다.

맨 마지막 줄에 visited를 false로 돌려놔야하는게 핵심이다.

아까의 input처럼 처음 C를 밟고 [1,0]에 있는 A를 밟았을때 visited를 체크하고 이걸 돌려놓지 않으면

[0,1]을 실행할 때 A를 밟지 못한다.

이것만 신경써서 풀어주면 쉬운 문제였다.

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력


첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력


첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

풀이


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static StringTokenizer st;
    static ArrayList<Integer>[] arr;
    static boolean[] visited;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        arr = new ArrayList[T+1];
        parent = new int[T+1];
        visited = new boolean[T+1];
        for (int i = 1; i<T+1; i++){
            arr[i] = new ArrayList<>();
        }
        for (int i=0; i<T-1; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[s].add(e);
            arr[e].add(s);
        }
        //DFS
        DFS(1);

        // 출력
        for (int i=2; i<T+1; i++){
            System.out.println(parent[i]);
        }
    }
    static void DFS(int x){
        visited[x] = true;
        for (int i : arr[x]){
            if (!visited[i]){
                parent[i] = x;
                DFS(i);
            }
        }
    }
}

해설


물론 전체적인 DFS 풀이의 기전은 비슷하지만, 여태까지 풀어본 DFS문제를 분류하라면, 크게 두개로 나눌 수 있다.

1. 전체 배열을 받아 연관관계를 찾고 영역의 개수 / 넓이를 찾는 문제

2. 일부 노드의 연관관계를 받아서 노드의 관계를 파악하는 문제

 

위의 문제는 2번에 속한다. 따라서 ArrayList<Integer>[] 배열을 이용함으로써 풀 수 있다.

    static StringTokenizer st;
    static ArrayList<Integer>[] arr;
    static boolean[] visited;
    static int[] parent;

그래서 ArrayList와 visited, 그리고 노드의 부모를 구해야 하므로 parent 배열을 선언한다.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        arr = new ArrayList[T+1];
        parent = new int[T+1];
        visited = new boolean[T+1];
        for (int i = 1; i<T+1; i++){
            arr[i] = new ArrayList<>();
        }
        for (int i=0; i<T-1; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[s].add(e);
            arr[e].add(s);
        }
        //DFS
        DFS(1);

        // 출력
        for (int i=2; i<T+1; i++){
            System.out.println(parent[i]);
        }
    }

ArrayList<Integer>[]같은 경우는 꼭 해줘야 할 것이, 선언한 후에 이를 초기화해주는 작업을 거쳐야 한다.

그리고 start와 end를 받아서 각 노드에 연결시켜준다.

예를 들어 4번 노드와 6번 노드가 연결되어 있다고 하면, 4번 노드에 6번을, 그리고 6번 노드에도 4번을 달아준다.

그리고 마지막으로 트리의 루트가 1이므로 DFS(1)을 실행시키고, 부모 노드의 리스트를 출력해주면 된다.

static void DFS(int x){
        visited[x] = true;
        for (int i : arr[x]){
            if (!visited[i]){
                parent[i] = x;
                DFS(i);
            }
        }
    }

DFS 함수같은 경우에는 각 ArrayList를 돌면서 방문하지 않았던 노드에 대해서 parent배열에 기입한다.

이 부분이 이해가 안 되는 사람이 있을 것이다. 예를 들면서 확인해보자.

7
1 6
6 3
3 5
4 1
2 4
4 7

1번 노드를 최상단 노드라고 하였으므로, 관계를 나타내면 다음과 같다.

1                                                                  
├─4──2
| └──7
└─6──3──5

DFS를 실행하기 전에 ArrayList의 내용을 찍어보면 다음과 같다.

for (ArrayList<Integer> i : arr){
 System.out.println("i = " + i);
}
===========
i = null
i = [6, 4]
i = [4]
i = [6, 5]
i = [1, 2, 7]
i = [3]
i = [1, 3]
i = [4]

이제 DFS를 실행했을 때의 경과를 보자.

DFS(1)을 실행하면 visited[1] 배열이 true로 바뀌고,

1번 배열의 [6, 4]에 대해서 재귀함수를 실행할 것인지를 물어본다.

6으로 넘어가서, 방문하지 않았으므로 방문했다는 체크를 하고 6의 parent는 1로 표기해놓는다.

그리고 DFS(6)을 실시한다. 6번 배열에는 [1,3]이 있고, 1은 표기했으므로 실행하지 않고 3번 노드로 넘어가서 3번 노드의 부모를 6으로 체크한다.

후의 노드에 대해서 전부 체크한다.

이런 식으로 흘러가는 간단한 ArrayList<Integer>[] 배열의 문제였다.

'알고리즘 > 백준' 카테고리의 다른 글

[백준/1260] - DFS와 BFS(JAVA)  (0) 2023.09.17
[백준/1526] - 내리막길(JAVA)  (0) 2023.09.15
[백준/1987] - 알파벳(JAVA)  (0) 2023.09.15
[백준/2468] - 안전 영역(JAVA)  (0) 2023.09.14
[백준/4963] - 섬의 개수(JAVA)  (2) 2023.09.14

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

풀이

public class Main{

    static StringTokenizer st;

    static int[][] land;
    static boolean[][] visited;

    static int N, count;

    //상 하 좌 우
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        land = new int[N][N];
        int maxHeight = 0;
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<N; j++){
                int h = Integer.parseInt(st.nextToken());
                land[i][j] = h;
                maxHeight = Math.max(maxHeight, h);
            }
        }
        int max = 0;
        //DFS
        for (int i=0; i<maxHeight; i++){
            count = 0;
            visited = new boolean[N][N];
            for (int j=0; j<N; j++){
                for (int k=0; k<N; k++){
                    if (!visited[j][k] && land[j][k] > i){
                        count++;
                        DFS(j, k, i);
                    }
                }
            }
            max = Math.max(max, count);
        }

        System.out.println(max);

    }

    static void DFS(int x, int y, int height){
        visited[x][y] = true;
        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >=0 && ny >= 0 && nx < N && ny < N){
                if (!visited[nx][ny] && (land[nx][ny] > height)){
                    DFS(nx, ny, height);
                }
            }
        }
    }
}

해설

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

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는

www.acmicpc.net

안전 영역과 비슷한 DFS계열 문제이다.

DFS의 핵심은 노드의 연결관계를 잘 파악해야 한다. 따라서 boolean 배열인 visited로 재방문을 막아야 한다.

 static StringTokenizer st;

    static int[][] land;
    static boolean[][] visited;

    static int N, count;

    //상 하 좌 우
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};

물이 잠기지 않는 지점은 대각선이 아닌, 가로와 세로로만 판단하므로 가로 세로만 있는 델타 배열을 이용한다.

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        land = new int[N][N];
        int maxHeight = 0;
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<N; j++){
                int h = Integer.parseInt(st.nextToken());
                land[i][j] = h;
                maxHeight = Math.max(maxHeight, h);
            }
        }
        int max = 0;
        //DFS
        for (int i=0; i<maxHeight; i++){
            count = 0;
            visited = new boolean[N][N];
            for (int j=0; j<N; j++){
                for (int k=0; k<N; k++){
                    if (!visited[j][k] && land[j][k] > i){
                        count++;
                        DFS(j, k, i);
                    }
                }
            }
            max = Math.max(max, count);
        }

        System.out.println(max);

    }

Main stack 안의 flow는 크게 다음의 2가지로 이루어진다.

 

1. 배열 채우기

2. DFS 사용하기

 

1. 배열 채우기

먼저 배열에 각 요소들을 담아준 뒤, 가장 높은 높이를 측정하기 위해서 maxHeight라는 변수를 설정하고 구한다.

 

2. DFS 사용하기

우리가 알고 싶은 것은 "연결되어있는 섬의 개수"이다.

전체 코드에서 DFS라는 단어가 들어가는 부분은 2부분이다.

[DFS를 사용하는 곳, DFS를 정의하는 곳]

이 두 군데 중 어느 곳에서 count를 늘리냐는 문제에서 구하라는 부분을 잘 읽고 나타내야 한다.

DFS를 사용하는 곳에서 count를 늘리면 "섬의 개수"를,

DFS를 정의하는 곳에서 count를 늘리면 "섬의 크기"를 구할 수 있게 된다.

우리는 섬의 개수를 구해야 하므로 DFS를 사용하는 곳에서 count를 늘려야 한다.

DFS를 시행하는 조건은 2개여야 한다.

1. 방문하지 않았을 것

2. 섬의 높이가 비가 오는 높이보다 초과해야 한다(>i)

 

static void DFS(int x, int y, int height){
        visited[x][y] = true;
        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >=0 && ny >= 0 && nx < N && ny < N){
                if (!visited[nx][ny] && (land[nx][ny] > height)){
                    DFS(nx, ny, height);
                }
            }
        }
    }

 

마지막으로 DFS 함수를 정의한다.

델타 배열을 정의하고, 좌표가 0 이상 N 미만일 시 비가 오는 지점보다 높다면 DFS함수를 재실행하면 된다.

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

풀이

public class bojtest2 {
	static StringTokenizer st;

	static int[][] land;
	static boolean[][] visited;

	static int N,M, count;

	//상 하 좌 우
	static int[] dx = {0,0,1,-1,-1,-1,1,1};
	static int[] dy = {1,-1,0,0,1,-1,1,-1};


	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		while (true){
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			if (N+M == 0) break;
			land = new int[M][N];
			visited = new boolean[M][N];
			for (int i = 0; i<M; i++){
				st = new StringTokenizer(br.readLine());
				for (int j=0; j<N; j++){
					land[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			// count 초기화
			count = 0;

			//DFS
			for (int i=0; i<M; i++){
				for (int j=0; j<N; j++){
					if(!visited[i][j] && land[i][j] == 1){
						count++;
						DFS(i, j);
					}
				}
			}
			sb.append(count).append("\n");
		}
		System.out.println(sb.toString());
	}

	static void DFS(int x, int y){
		visited[x][y] = true;
		for (int i=0; i<8; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < M && ny < N){
				System.out.println("nx , ny");
				if (!visited[nx][ny] && land[nx][ny] == 1){
					DFS(nx, ny);
				}
			}
		}
	}
}

해설

DFS 정복 주간 처음으로 풀어본 문제이다.

이런 길찾기류 문제가 DFS의 대표적인 유형이다.

DFS의 핵심은 노드의 연결관계를 잘 파악해야 한다. 따라서 boolean 배열인 visited로 재방문을 막아야 한다.

static StringTokenizer st;

static int[][] land;
static boolean[][] visited;

static int N,M, count;

//상 하 좌 우 대각선
static int[] dx = {0,0,1,-1,-1,-1,1,1};
static int[] dy = {1,-1,0,0,1,-1,1,-1};

문제를 보면 앞뒤, 위아래, 그리고 대각선까지 연결하는 것이 같은 땅이라고 해석하고 있다.

그래서 dx, dy를 델타 배열로 주었다.

public static void main(String[] args) throws IOException {
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 StringBuilder sb = new StringBuilder();
 while (true){
  st = new StringTokenizer(br.readLine());
  N = Integer.parseInt(st.nextToken());
  M = Integer.parseInt(st.nextToken());
  if (N+M == 0) break;
  land = new int[M][N];
  visited = new boolean[M][N];
  for (int i = 0; i<M; i++){
   st = new StringTokenizer(br.readLine());
   for (int j=0; j<N; j++){
    land[i][j] = Integer.parseInt(st.nextToken());
   }
  }
// count 초기화
 count = 0;

//DFS
 for (int i=0; i<M; i++){
  for (int j=0; j<N; j++){
   if(!visited[i][j] && land[i][j] == 1){
     count++;
     DFS(i, j);
    }
   }
  } 
  sb.append(count).append("\n");
 }
 System.out.println(sb.toString());
}

Main stack 안의 flow는 크게 다음의 2가지로 이루어진다.

 

1. 배열 채우기

2. DFS 사용하기

 

1. 배열 채우기

먼저, 0 0이 주어져야 끝나므로 breakpoint를 걸어둔다.

숫자를 입력받고, land와 visited 배열을 초기화 시켜주고,

섬의 개수를 나타낼 count를 초기화시켜준다.

 

2. DFS 사용하기

우리가 알고 싶은 것은 "연결되어있는 섬의 개수"이다.

전체 코드에서 DFS라는 단어가 들어가는 부분은 2부분이다.

[DFS를 사용하는 곳, DFS를 정의하는 곳]

이 두 군데 중 어느 곳에서 count를 늘리냐는 문제에서 구하라는 부분을 잘 읽고 나타내야 한다.

DFS를 사용하는 곳에서 count를 늘리면 "섬의 개수"를,

DFS를 정의하는 곳에서 count를 늘리면 "섬의 크기"를 구할 수 있게 된다.

우리는 섬의 개수를 구해야 하므로 DFS를 사용하는 곳에서 count를 늘려야 한다.

DFS를 시행하는 조건은 2개여야 한다.

1. 방문하지 않았을 것

2. 섬이라는 표시(1)가 되어있을 것

static void DFS(int x, int y){
 visited[x][y] = true;
 for (int i=0; i<8; i++){
  int nx = x + dx[i];
  int ny = y + dy[i];
   if (nx >= 0 && ny >= 0 && nx < M && ny < N){
    if (!visited[nx][ny] && land[nx][ny] == 1){
     DFS(nx, ny);
    }
   }
  }
 }

마지막으로 DFS 함수를 정의한다.

우리가 방문하게 되면 방문했다고 표기를 해야 하므로 visited배열을 true값으로 바꿔준다.(초기화시 false)

또 델타 배열을 돌면서 판단하는데, 배열을 돌 때는 늘 Array의 크기 안에 좌표가 있어야 한다.(nx의 조건)

방문하지 않았고(!visited[x][y]) 섬이라는 표시(land[nx][ny] == 1)가 되어있으면 (nx, ny)의 좌표로 넘어가서

DFS를 새로 시행한다는 함수다.

 

이러한 유형의 문제는 

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

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는

www.acmicpc.net

에서 한 번 더 연습할 수 있다.

탐색

탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘을 말합니다.
주어진 데이터의 성질(정렬 데이터 또는 비정렬 데이터)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요하고, 모든 코딩 테스트 문제의 기본이 되는 알고리즘이라 직접 구현해 원리를 완벽하는 것이 중요합니다.

깊이 우선 탐색

깊이 우선 탐색(DFS : depth-first search)는 그래프 완전 탐색 기법 중 하나입니다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발해 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘입니다.

기능 특징 시간복잡도(노드 수 : V, 엣지 수 : E)
그래프 완전 탐색 - 재귀 함수로 구현
- 스택 자료구조 이용
O(V+E)

깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로우(stack overflow)에 유의해야 합니다. 깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있습니다.

DFS의 핵심 이론

DFS는 한 번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인접 리스트로 표현하겠습니다. 그리고 DFS의 탐색 방식은 후입선출(LIFO) 특성을 가지므로 스택을 사용하여 설명하겠습니다.

  • 여기서는 설명의 편의를 위해 스택을 사용했습니다. 그렇지만 DFS 구현은 스택보다는 스택 성질을 갖는 재귀 함수로 많이 구현합니다.

그림

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드를 스택에 삽입하기 입니다. 스택에 시작 노드를 1로 삽입할 때 해당 위치의 방문 배열을 체크하면 T,F,F,F,F,F가 됩니다.

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
이제 pop을 수행하여 노드를 꺼냅니다. 꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하며 방문 배열을 체크합니다. 방문 배열은 T,T,T,F,F,F가 됩니다.

3. 스택 자료구조에 값이 없을 때까지 반복하기
앞선 과정을 스택 자료구조에 값이 없을 때까지 반복합니다. 이 때, 이미 다녀간 노드는 방문배열을 바탕으로 재삽입하지 않는 것이 핵심입니다.

풀어볼 문제

문제 023 - 연결 요소의 개수 구하기(11724)

문제 024 - 신기한 소수 찾기(2023)

문제 025 - 친구 관계 파악하기(13023)

'알고리즘' 카테고리의 다른 글

우선순위 큐를 이용한 그리디 문제  (0) 2023.10.15
이진 탐색, 이분 탐색  (0) 2023.10.04
구간합 & 투 포인터 & 슬라이딩 윈도우  (0) 2023.09.27
탐색(2) - BFS  (0) 2023.09.17
DP  (0) 2023.09.07

DP

동적 계획법(dynamic programming)은 복잡한 문제를 여러개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻합니다.

동적 계획법의 핵심 이론

동적 계획법의 원리와 구현 방식은 다음과 같습니다.

동적 계획법의 원리와 구현 방식

  1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
  2. 작은 문제들이 반복되어 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.
  3. 모든 작은 문제들은 한 번만 계산해 DP테이블에 저장하며 추후 재사용할 때는 이 DP테이블을 이용한다. 이를 메모이제이션(memoization)기법이라고 한다.
  4. 동적 계획법은 톱-다운 방식(top-down)과 바텀-업 방식(bottom-up) 방식으로 구현할 수 있다.

동적 계획법의 예

피보나치 수열을 예로 들어 설명한다.

D[N] = D[N-1] + D[N-2]
  1. 동적 계획법으로 풀 수 있는지 확인하기
    6번째 피보나치 수열은 5번째 피보나치 수열과 4번째 피보나치 수열의 합이다. 즉 6번째 피보나치 수열을 구하는 문제는 5번째 피보나치 수열과 5번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있고, 수열의 값은 항상 같기 때문에 동적 계획법으로 풀 수 있다.
  2. 점화식 세우기
    점화식을 세울 때는 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는 훈련이 필요합니다. 이 부분은 다양한 실전 문제를 풀면서 자연스럽게 훈련됩니다.
  3. 메모이제이션 원리 이해하기
    메모이제이션은 부분 문제를 풀었을 때 이 문제를 DP테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP테이블의 값을 이용하는 것을 말합니다. 다음 그림을 보면 위에서 2번째와 3번째 피보나치 수열은 맨 왼쪽 탐색 부분에서 최초로 값이 구해지고, 이때 DP테이블에 값이 저장됩니다. 이에 따라 나중에 2번째와 3번째 피보나치 수열의 값이 필요할 때 재연산을 이용해 구하지 않고, DP테이블에서 바로 값을 추출합니다. 이러한 방식을 사용하면 불필요한 연산과 탐색이 줄어들어 시간 복잡도 측면에서 많은 이점을 가질 수 있습니다.
  4. 톱-다운 구현 방식 이해하기
    톱-다운 구현 방식은 말 그대로 위에서부터 문제를 파악해 내려오는 방식으로, 주로 재귀(recursion)함수 형태로 코드를 구현합니다. 코드의 가독성이 좋고, 이해하기가 편하다는 장점이 있습니다.
public class TopDown{
    static int[] dp;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        dp = new int[T+1];
        for (int i=0; i<=T; i++){
            dp[i] = -1;
        }
        dp[0] = 0;
        dp[1] = 1;
        fibonacci(T);
        System.out.println(dp[T]);
    }
    static int fibonacci(int N){
        // 기존에 계산한 적이 있는 부분의 문제는 재계산하지 않고 리턴한다.
        if (dp[N] != -1) return dp[N];
        //메모이제이션 : 구한 값을 바로 리턴하지 않고 DP테이블에 저장한 후 리턴하도록 로직을 구현한다.
        return dp[n] = fibonacci(n-2) + fibonacci(n-1);
    }
}
  1. 바텀-업 구현 방식 이해하기
    가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식입니다. 주로 반복문의 형태로 구현합니다.
    public class BottomUp{
     static int[] dp;
     public static void main(String[] args){
         Scanner sc = new Scanner(System.in);
         int T = sc.nextInt();
         dp = new int[T+1];
         for (int i=0; i<=T; i++){
             dp[i] = -1;
         }
         dp[0] = 0;
         dp[1] = 1;
         for (int i=2; i<= T; i++){
             dp[i] = dp[i-1] + dp[i-2];
         }
         System.out.println(dp[T]);
     }
    }

두 방식 중 좀 더 안전한 방식은 바텀-업입니다. 톱-다운 방식은 재귀 함수의 형태로 구현돼어 있기 때문에 재귀의 깊이가 매우 깊어질 경우 런타임 에러가 발생할 수 있습니다. 하지만 실제 코테에서 이 부분까지 고려해야 하는 난이도는 잘 나오지 않습니다. 자신에게 좀 더 편한 방식이나 문제에 따라 두 방식 중 1개를 선택해 사용하면 됩니다.

'알고리즘' 카테고리의 다른 글

우선순위 큐를 이용한 그리디 문제  (0) 2023.10.15
이진 탐색, 이분 탐색  (0) 2023.10.04
구간합 & 투 포인터 & 슬라이딩 윈도우  (0) 2023.09.27
탐색(2) - BFS  (0) 2023.09.17
탐색(1) - DFS  (0) 2023.09.11

과거에 html 도큐먼트를 읽기 위해서 개발된 HTTP 프로토콜을 더욱 더 발전시키기 위해서

설계 매커니즘에는 UI / 데이터 / 제어체계를 분리시키자는, 이른바 MVC 패턴이 등장했다.

이에 UI와 데이터를 분리시키는 과정에서 데이터는 Json이나 XML로 보내고,

UI는 자바스크립트 기반 언어를 이용해서 위에서 받은 자료를 가지고 동적으로 HTML을 생성하게 되었다.

이 기술은 유저들이 사용하는 디바이스가 점점 더 많아짐에 따라(각 디바이스마다 인치수가 다르므로)

독립된 기술로 발전했는데, 바로 React.js와 Vue.js 같은 툴의 등장 되시겠다.

그리고 이것을 넘어서서, React의 기능을 기반으로 SSR을 하기 위해 나온 풀스택 웹 어플리케이션 프레임워크인

Next.JS가 등장했다.

Next.JS는 React 기술 기반인 만큼 프론트엔드는 리액트로 구현하고, 백엔드는 Express.JS와 비슷한 원리로 구현된다.

풀스택 프레임워크인 만큼, 개발자는 더 이상 프론트에 3000 포트를 띄움과 동시에, 백엔드에 8080 포트를 띄울 필요성이 없어졌고, CORS같은 복잡한 설정도 할 필요 없이 개발에만 집중하면 되는 장점을 누릴 수 있다.

CSR과 SSR은 서로 장단점을 가지고 있지만, SSR방식을 채택할 경우 유저에게 더 빠른 페이지 로드와

자바스크립트가 있지 않아도 서버에서 html 도큐먼트를 생성해서 클라이언트에 보낸다는 점에서 SEO(검색 엔진)과 같은 로봇에게도 친화적이다. 그래서 내가 만든 웹 어플리케이션을 남들에게도 더 많이 알릴 수 있다는 장점또한 존재한다.

이 글에서는 Next.JS 13을 다룰 것이다. Next는 App Router를 위해 기존 버전과의 하위호환성을 전부 버릴 정도로 큰 결심을 단행했다. 하위호환성을 가장 중요시하는 Java/Spring과는 확연히 다른 행보이며, 이 App Router가 무엇이길래 Next.JS가 하위호환성을 포기했는지부터 알아보자.

App Router란 무엇일까?

공식 문서(https://nextjs.org/docs/app/building-your-application/routing)에서는 App routing을 다음과 같이 설명하고 있다.

In version 13, Next.js introduced a new App Router built on React Server Components, which supports shared layouts, nested routing, loading states, error handling, and more.

버전 13에서 Next.js 는 공유 레이아웃, 중첩 라우팅, 로딩 상태, 오류 처리 등을 지원하는 React Server Components를 기반으로 구축된 새로운 앱 라우터를 도입했습니다.

Next.js는 기존의 '페이지 라우터'라는 기술을 버리고, 새롭게 '앱 라우터'라는 기술을 도입할 만큼 '라우터'를 기반으로 동작한다.

라우터

라우터가 무엇이냐고 물으면, 나는 '표지판'이라고 대답할 것이다.

라우터는 데이터에게 어디로 가야하는지에 대한 경로를 표시해 주기도 하고, 특정 데이터를 어디에 보내는 '라우팅'의 역할도 한다.

앱 라우터는 src/app 밑에서 동작하는데, file system(directory)를 기준으로 데이터를 보낸다.

예를 들어 내가 'localhost:3000/create' 페이지를 만들고 싶으면,

src/app                                                                        
├─layout.js
├─page.js
└─create
  └─page.js

이렇게 만들면 된다는 것이다.

과거의 페이지 라우터는 다음과 같은 방식으로 만들었어야 했다.

src/pages                                                                        
├─_app.js
├─index.js
└─create.js

이러다 보니, 전체 페이지가 난잡해질 뿐 아니라 코드가 복잡해지면 js파일이 너무 무거워진다는 단점또한 존재한다.

앱 라우터는 페이지 라우터보다 먼저 동작하고,리액트 서버 컴포넌트를 기반으로 구축된다.

앱 라우터와 페이지 라우터의 비교에 대한 추가적인 설명은

https://www.timegambit.com/blog/blog-log/app-router

를 보면 이해하기 쉽다.

Server Component

서버 컴포넌트란 무엇인가?

리액트18부터 도입된 리액트 서버 컴포넌트는 기존의 컴포넌트로 인식된 '클라이언트 컴포넌트'와는 다르게

서버에서 컴포넌트를 렌더링한 후 제공한다.

이를 위해선 하이드레이션(Hydration)이 무엇인지 알 필요가 있다.

클라이언트에서 한꺼번에 조립되는 CSR방식과는 달리,

SSR에서는 서버에서 먼저 완성된 정적인 HTML 도큐먼트를 클라이언트에 보내고, 리액트에서 JS를 번들링(이미지, 폰트, CSS등을 js로 변경해서 보내는 것)해서 보내면 클라이언트에서 이를 조립해서 동적인 페이지로 변화시키는 것이다.

이를 '물에 준다'는 뜻으로, Hydrate라고 부른다.

일반적으로, 서버 컴포넌트들은 Hydrate 이후에는 재사용 할 수 없다.

그러나 React server component를 사용하면 hydrate 이후에도 컴포넌트들을 사용할 수 있다.

그래서 RSC(React Server Component)는 SSR과 함께하는 개념이라기보다는, SSR을 보완해주는 개념이라고 볼 수 있다.

서버 컴포넌트 vs 클라이언트 컴포넌트

서버 컴포넌트

  • 서버에서 직접 데이터 가져오기
  • 보안에 민감한 정보에 안전하게 접근
  • 렌더링에 필요한 라이브러리를 번들에 포함하지 않음으로써 JS 사이즈 줄이기

클라이언트 컴포넌트

  • onClick, onChange와 같은 이벤트 리스너
  • useState, useReducer, useEffect와 같은 상태와 생명주기
  • browser에서 사용할 수 있는 api
  • state, effect, brower api를 사용하는 커스텀 훅

이렇게 서버 클라이언트와 클라이언트 컴포넌트가 하는 일은 명확하게 구분되어있다. 그래서 가장 중요한 것이

이 컴포넌트들을 적재적소에 잘 이용하는 것이다.

그리고 클라이언트 컴포넌트를 이용하기 위해서는 'use client'를 명시해주면 되는데, 이는 다음에 확인하자.

참조

App router / Pages router 비교

Server components

hydration

+ Recent posts