결론을 말하자면 인덱스는 B+TREE 방식이 사용된다.

B-TREE와 B+TREE는 어떤 차이가 있고, 왜 DB 인덱스는 B+TREE가 쓰이는지 알아보자.

이진 트리

B-TREE를 설명하자고 해놓고, 왜 이진 트리부터 설명하는가.

B-TREE는 결국 이진 트리에서 파생된 자료구조이기 때문에 이진 트리에 대해 정확히 짚고 넘어가려고 한다.

이진 트리는 모든 노드가 최대 2개(0~2)의 하위 노드를 갖는 트리 자료구조이다.

트리의 구성 요소는 다음과 같다.

부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장한다.

데이터가 많아질 수록 비교 횟수가 증가하여 추가, 삭제에 시간이 더 걸린다.

이런 이진 트리에는 몇 가지 종류가 존재한다.

1. 정 이진 트리 (full binary tree)

   • 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
   • 중간에 1개의 자식만 가진 노드가 없다.

2. 포화 이진 트리 (perfect binary tree)

• 모든 내부 노드가 정확히 2개의 자식을 가지며, 모든 리프 노드가 같은 레벨에 있다.
• 가장 이상적인 형태이지만, 실제 데이터로 이런 구졸르 만들기 어렵다.

3. 완전 이진 트리 (complete binary tree)

• 마지막 레벨을 제외한 모든 레벨이 채워져 있다.
• 마지막 레벨은 왼쪽부터 차례로 채워진다.
• 힙 자료구조 등에서 사용되며, 효율적인 메모리 사용이 가능하다.

4. 균형 이진 트리 (balanced binary tree)

• 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1이다.
• 이 구조는 트리의 균형을 유지하여 효율적인 연산을 가능하게 한다.

등등.. 종류가 더 있지만 주요 이진 트리만 가져와봤다.

이 중에 균형 이진 트리가 실제 응용 분야(데이터베이스 인덱싱, 파일 시스템, 네트워크 라우팅 테이블 등)에서 많이 사용된다.

이미 눈치 챈 사람도 있겠지만, 균형 이진 트리의 Balanced의 B를 따서 B-TREE, B+TREE라고 칭하는 것이다.

B-TREE

B-TREE는 이진 트리와 다르게 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.

하나의 노드 최대 자식수가 3개이면 3차 B-TREE, 4개면 4차 B-TREE 라고 한다.

최대 자식수의 개수에 따라서 1,2,3..M차 B-TREE가 있다.

1. 최대 자식 노드 개수: B-TREE의 각 노드는 최대 M개의 자식을 가질 수 있다.

2. 비리프 노드의 키 개수: 자식 노드가 K개인 비리프 노드는 항상 K-1개의 키를 가지고 있다. 이 키들은 자식 노드들이 저장한 값들을 구간으로 나눠주는 역할을 한다.

3. 최소 자식 노드 개수: 모든 내부 노드는 최소 ⌈M/2⌉개의 자식을 가져야 한다. 즉, 한 노드가 가질 수 있는 자식 노드의 개수는 적어도 트리의 차수(M)의 절반이다. (B-트리에서 최소 자식 노드 개수를 결정할 때는 항상 올림을 사용)

4. 리프 노드의 동일 레벨: 모든 리프 노드들은 동일한 레벨에 존재해야 한다. 이는 트리가 항상 균형을 유지하도록 보장하여, 트리의 높이가 일정하게 유지되게 한다.

5. 리프가 아닌 노드의 최소 자식 수: 리프가 아닌 모든 노드는 최소 2개의 자식을 가져야 한다. 즉, 루트가 아니면서 자식이 없는 노드는 존재할 수 없다.

아래는 3차 트리의 예시를 보여준다.

각 특징을 반영하여 가정할 수 있는 예시이다.

B-TREE 시뮬레이션

위 링크로 들어가면 B-TREE가 어떻게 구성되는지를 시뮬레이션으로 시각화하여 이해를 돕고 있다.

B+TREE

B-TREE는 내부 노드와 리프 노드에 모두 데이터를 저장하는 반면에 B+TREE는 데이터를 리프 노드에만 저장하고, 내부 노드는 오직 키 값만 저장한다.

B+ 트리는 리프 노드가 연결 리스트로 연결되어 있어 순차 검색이 빠르다.

B+ 트리는 리프 노드를 순차적으로 연결하는 포인터 집합을 가지고 있다. 이를 통해 인덱스된 순차 파일을 처리할 때, 포인터를 사용해 키와 값을 일일이 비교하지 않고도 다음 데이터에 빠르게 접근할 수 있어 효율적인 처리가 가능하다.

B-TREE 시뮬레이션

동일하게 위 링크로 들어가면 B+TREE가 어떻게 구성되는지를 시뮬레이션으로 시각화하여 이해를 돕고 있다.

B-TREE vs B+TREE

시뮬레이션을 통해 B-TREE와 B+TREE가 어떻게 다른지 비교해보자.

1~10까지 숫자를 예제로 비교해보았다.

먼저 B-TREE이다.

루트 노드 : 7

내부 노드 : 3, 5, 9

리프 노드 : 1, 2, 4, 6, 8, 10

다음은 B+TREE이다.

루트 노드와 내부 노드는 동일한 형태를 띄지만, 리프 노드 형태가 조금 다른 것을 확인할 수 있다.

B+TREE는 리프 노드에 루트 노드와 내부 노드가 포함되며, 연결 리스트로 연결되어 있다.

B-TREE는 탐색을 위해 노드를 찾아 이동해야하지만, B+TREE는 리프 노드에 모든 키값들이 정렬되어 있기 때문에 탐색에 있어 더 유리하다.

위 그림은 InnoDB에서 사용되는 B+TREE 구조이다.

InnoDB는 B+TREE 보다 더 복잡하다.

InnoDB에서는 같은 레벨의 노드들끼리는 Linked List가 아닌 Double Linked List로 연결되었으며, 자식 노드들은 Single Linked List로 연결되어 있다.

B+Tree 구조에서는 각 키의 범위에 따라 다음에 가야 할 페이지 넘버를 가리키는 포인터가 있다. 이 포인터를 통해 빠르게 다음 노드로 넘어갈 수 있다.

리프 노드에 도착하면, 여기서 디스크에 저장된 데이터의 주소를 확인할 수 있다. 또한, 리프 노드는 Linked List로 연결되어 있어, 이 리스트를 통해 데이터를 순차적으로 탐색할 수 있는 것이다.

데이터베이스 인덱스 [mysql]

데이터베이스에서 인덱스는 데이터를 조회할 때 모든 레코드에서 찾는게 아니라 검색 대상 레코드 범위를 줄일 수 있게 해준다.

CREATE TABLE employee (
    emp_no INT NOT NULL AUTO_INCREMENT,
    name VARCHAR(64) NOT NULL,
    department VARCHAR(64),
    hire_date DATE,
    PRIMARY KEY (emp_no),
    INDEX idx_name (name),
    INDEX idx_department (department)
);

예시로 employee라는 테이블을 만들어 보았다.

이 CREATE TABLE 문은 idx_name과 idx_department라는 두 개의 인덱스를 포함하고 있다.

이 테이블에 대해 인덱스를 활용한 SELECT 문의 예를 몇 가지 들어보면 다음과 같다.

1. 이름으로 검색 (idx_name 인덱스 사용):

   SELECT * FROM employee WHERE name = '홍길동';

2. 부서로 검색 (idx_department 인덱스 사용):

SELECT * FROM employee WHERE department = '개발팀';

3. 부서별 직원 수 조회 (idx_department 인덱스 사용):

   SELECT department, COUNT(*) as employee_count 
   FROM employee 
   GROUP BY department;

4. 이름과 부서로 동시에 검색 (복합 조건에서 두 인덱스 모두 활용 가능):

   SELECT * FROM employee 
   WHERE name LIKE '김%' AND department = '인사팀';

이러한 쿼리들은 idx_name과 idx_department 인덱스를 활용하여 검색 속도를 향상시킬 수 있다. 대량의 데이터에서 특정 이름이나 부서를 검색할 때 효과적이다.

인덱스의 효과를 확인하려면 EXPLAIN 명령어를 쿼리 앞에 붙이면 확인할 수 있다.

EXPLAIN SELECT * FROM employee WHERE name = '홍길동';

실제로 사용된 인덱스가 idx_name 이고, extra를 보면 Using index condition라고 출력한다. 이는 인덱스를 효과적으로 활용하고 있다는 것을 의미한다.

테이블의 인덱스를 보면 Index_type이 BTREE인 것을 확인할 수 있다.

이런 인덱스 사용은 기본 원칙을 따르면, SQL 문을 더욱 효율적으로 작성할 수 있을 것이다.

인덱스 사용의 기본 원칙

1. INSERT, UPDATE, DELETE 작업이 많은 경우 인덱스 사용 자제

쓰기 작업이 빈번한 테이블에는 인덱스를 최소한으로 사용하는 것이 좋다.

인덱스는 데이터를 삽입하거나 수정, 삭제할 때마다 인덱스 구조를 업데이트해야 하기 때문에 쓰기 성능을 저하시킬 수 있다.

2. 조건절을 사용한 SELECT(읽기) 작업이 많은 경우 인덱스 사용

데이터 검색, 조회, 정렬, JOIN, 집계 등에서 성능을 높이기 위해 인덱스를 사용하는 것이 좋다.

특히 다음과 같은 상황에서 인덱스를 사용하면 효율적이다.

검색 쿼리가 자주 발생할 때: WHERE 조건에 자주 사용되는 열에 인덱스를 추가하면 검색 속도가 빨라진다.

정렬이 자주 필요할 때: ORDER BY가 자주 사용되는 열에 인덱스를 추가하면 성능이 향상된다.

JOIN을 자주 사용할 때: 테이블 간의 JOIN에 사용되는 열(기본 키 또는 외래 키)에 인덱스를 추가하면 JOIN 성능이 크게 개선된다.

집계 함수(GROUP BY, COUNT, SUM, MAX, MIN)를 사용할 때: 인덱스가 집계 작업의 속도를 높여준다.

출처

위키백과: 이진 트리

위키백과: B- 트리

위키백과: B+ 트리

B+Tree index structures in InnoDB

A* Algorithm

A* 알고리즘

주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘 중 하나이다.

이 알고리즘은 다익스트라 알고리즘과 유사하나 차이점은 각 꼭짓점 x에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 순위값인 휴리스틱 추정값 h(n)을 매기는 방법을 이용한다는 것이다.

휴리스틱 추정값

가용한 정보를 기반으로 각 분기 단계에서 어느 한 분기를 선택하기 위해 사용하는 다양한 탐색 알고리즘의 대안 함수이다.

방법은 두 가지로 나눌 수 있다.

(1) 잘못 배치된 타일의 수를 세는 것 (2) 각 블록의 현재 위치와 목표 위치 사이의 Manhattan distance(맨하탄 거리)의 합을 구하는 것

다시 한번 말하자면 A* 알고리즘은 출발 꼭짓점으로부터 목표 꼭짓점까지 최적 경로를 탐색하기 위한 것이다.

이를 위해서는 각각의 꼭짓점에 대한 평가 함수를 정의해야 한다. 평가함수 f(n)은 다음과 같다.

f(n) = g(n) + h(n)

• g(n): 출발 꼭짓점으로부터 꼭짓점 n까지의 경로 가중치
• h(n): 꼭짓점 n으로부터 목표 꼭짓점까지의 추정 경로 가중치

이 f(n)이 작은 값부터 탐색하는 특성 상 우선순위 큐가 사용된다.

동작 순서는 다음과 같다.

1. f(x) 를 오름차순 우선순위 큐에 노드로 삽입한다.

2. 우선순위 큐에서 최우선 노드를 꺼낸다.

3. 해당 노드에서 이동할 수 있는 노드를 찾는다.

4. 그 노드들의 f(x) 를 구한다.

5. 그 노드들을 우선순위 큐에 삽입한다.

6. 목표 노드에 도달할 때까지 반복한다

이 부분이 다익스트라 알고리즘과 유사점이 존재한다.

다익스트라 알고리즘과의 유사점

1. 우선순위 큐 사용 다익스트라: 최소 거리를 가진 노드를 선택하기 위해 우선순위 큐를 사용한다. A*: 우선순위 큐를 사용해 f(n) 값이 가장 작은 노드를 선택한다.

2. 그리디한 접근 다익스트라: 항상 현재까지 알려진 최단 경로를 선택한다. A*: f(n) = g(n) + h(n)이 최소인 노드를 선택하여 탐색한다.

3. 방문 노드 관리 다익스트라와 A* 모두 이미 방문한 노드를 다시 방문하지 않는다.

예시: 8-Puzzle

• 3x3 숫자판에 1~8까지의 숫자와 빈칸이 주어져 있다고 가정

• 숫자를 인접한 빈칸으로 옮기는 작업을 반복함으로써 주어진 숫자 배열로부터 목표가 되는 숫자 배열로 바꾸되, 숫자의 총 이동 횟수를 최소로 한다.

• 이를 A* 알고리즘 으로 풀어보자

코드

먼저 전체 코드는 다음과 같다.

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static String startNode;
    static String goalNode;
    static int[] moveRow = {-1, 0, 1, 0};
    static int[] moveCol = {0, 1, 0, -1};
    static HashMap<String, Integer> visitMap = new HashMap<>(); //한 번의 테스트 시 방문 여부 체크: 순서X 중복(키X,값O)
    static PriorityQueue<Puzzle> pq = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        System.out.println("아래에 목표 노드를 3x3 형태로 입력해주세요. (빈 퍼즐은 숫자 대신 #을 입력해주세요)"); //목표 노드 입력
        StringBuilder sbGoalBoard = new StringBuilder();
        for (int i = 0; i < 3; i++) {
            sbGoalBoard.append(br.readLine());
        }
        goalNode = sbGoalBoard.toString();

        System.out.println("아래에 시작 노드를 3x3 형태로 입력해주세요. (빈 퍼즐은 숫자 대신 #을 입력해주세요)"); //시작 노드 입력
        StringBuilder sbStartBoard = new StringBuilder();
        for (int i = 0; i < 3; i++) {
            sbStartBoard.append(br.readLine());
        }
        startNode = sbStartBoard.toString();

        //시작 노드 우선순위_큐에 담음 (f(n)=g(n)+h(n)이지만, g(n)이 0이므로 f(n)에는 h(n)만 대입)
        pq.add(new Puzzle(startNode, getHeuristic(startNode), 0, getHeuristic(startNode)));
        //시작 노드 재방문_방지_map에 저장
        visitMap.put(startNode, 0);

        boolean reachedGoal = aStar(); //a* 알고리즘
        if (reachedGoal) {
            bw.write(String.valueOf("최소한의 이동 횟수: "+visitMap.get(goalNode)+ "\n"));
        } else {
            bw.write("해당 시작노드는 목표노드로 이동할 수 없습니다." + "\n");
        }
        bw.flush();
        bw.close();
    }

    private static boolean aStar() throws IOException {
        StringBuilder stepsLog = new StringBuilder(); // 성공 시 출력할 로그를 저장
        stepsLog.append("\n");

        while (!pq.isEmpty()) {
            Puzzle currentPuzzle = pq.poll();
            String currentData = currentPuzzle.node;
            int currentStep = currentPuzzle.g; // 현재 노드의 깊이

            if (currentData.equals(goalNode)) {
                //목표 노드까지 stringbuilder에 추가
                consoleLog(stepsLog, currentPuzzle, goalNode);
                stepsLog.append("\n");
                bw.write(stepsLog.toString());
                // 목표 상태에 도달했을 때만 로그를 출력
                bw.write("목표 상태에 도달했습니다!\n");
                return true;
            }
            //시작 노드부터 목표노드 이전까지 선택된 노드를 stringbuilder에 추가
            consoleLog(stepsLog, currentPuzzle, currentData);

            int emptyPlaceIndex = currentData.indexOf("#");
            int currentRow = emptyPlaceIndex / 3;
            int currentCol = emptyPlaceIndex % 3;

            for (int i = 0; i < 4; i++) {
                int newRow = currentRow + moveRow[i];
                int newCol = currentCol + moveCol[i];
                if (newRow >= 0 && newRow < 3 && newCol >= 0 && newCol < 3) {
                    StringBuilder nextData = new StringBuilder(currentData);
                    nextData = swap(currentRow, currentCol, newRow, newCol, nextData);
                    String data = nextData.toString();

                    if(visitMap.containsKey(data)) continue; //이미 본 케이스라면 건너뛴다.
                    else {
                        int g = currentStep + 1; //경로가중치+1
                        int h = getHeuristic(data);
                        int f = g + h;
                        pq.add(new Puzzle(data, f, g, h));
                        visitMap.put(data, g);
                    }
                }
            }
        }
        return false;
    }

    private static void consoleLog(StringBuilder stringBuilder, Puzzle currentPuzzle, String data) {
        stringBuilder.append("(1) f(n): " + currentPuzzle.f+", g(n): " + currentPuzzle.g+", h(n): " + currentPuzzle.h).append("\n");
        stringBuilder.append("(2) 이동 횟수: " + currentPuzzle.g).append("\n");
        for (int i = 0; i < 3; i++) {
            stringBuilder.append(data.substring(i * 3, i * 3 + 3)).append("\n");
        }
        stringBuilder.append("---------").append("\n");
    }

    private static int getHeuristic(String data) {
        // 목표노드 인덱스 위치의 숫자 값이 동일한지 확인 (h(n)은 작을 수록 좋은 것)
        // 휴리스틱 방법 Manhattan Distance로 해도 상관없음
        int cnt = 0;
        for (int i = 0; i < data.length(); i++) {
            if(data.charAt(i) == '#') continue;
            else if (goalNode.charAt(i) != data.charAt(i)) cnt++; //같은 위치에 같은 숫자가 아니라면 cnt++
        }
        return cnt;
    }

    private static StringBuilder swap(int currentRow, int currentCol, int newRow, int newCol, StringBuilder nextData) {
        int currentRC = currentRow * 3 + currentCol; //이차원 배열의 row, col 을 nextData에서 추출 가능하게 일차원 형태로 변환 (빈공간 위치 인덱스)
        int nextRC = newRow * 3 + newCol; //이차원 배열의 row, col 을 nextData에서 추출 가능하게 일차원 형태로 변환 (변경할 값이 있는 인덱스)
        char temp = nextData.charAt(currentRC);
        nextData.setCharAt(currentRC, nextData.charAt(nextRC));
        nextData.setCharAt(nextRC, temp);
        return nextData;
    }


    static class Puzzle implements Comparable<Puzzle>{
        String node;
        int f; //f(n)
        int g; //g(n)
        int h; //h(n)

        @Override
        public int compareTo(Puzzle o) {
            if(f == o.f) return Integer.compare(g, o.g); //f(n)이 동일하다면 이동 횟수가 작은 수 선택
            return Integer.compare(f, o.f); //f(n)기준으로 작은 수 선택
        }

        public Puzzle(String node, int f, int g, int h) {
            this.node = node;
            this.f = f;
            this.g = g;
            this.h = h;
        }
    }
}

전제

• 목표 노드와 시작 노드를 입력받는다.

  • 단, 빈 퍼즐은 숫자 대신 #을 쓴다 (1~8 + #)

• 시작 노드에서 목표 노드로 도달하는데 있어 이동 횟수 및 퍼즐 이동 형태를 콘솔로 출력한다.

• 마지막엔 최소 이동 횟수를 출력한다.

• 이동이 불가능한 경우엔 이동 횟수 및 퍼즐 이동 형태를 생략하고, 이동 불가 메세지를 출력한다.

해결과정

0. 정적 멤버(=클래스 멤버)로 선언한 변수들

1. 입력 받은 목표 노드와 시작 노드를 한 줄의 문자열로 바꾼다.

2. 문자열 형태의 시작 노드를 우선순위 큐에 담아 주었다. (시작 노드(String), f(n), g(n), h(n))

   참고로 우선 순위 큐인 PriorityQueue는 f(n) 값이 가장 작은 노드가 우선권을 가지게 한다.

   f(n) 값이 동일한 노드끼리인 경우 g(n)이 더 작은 노드가 우선권을 가진다.

3. HashMap을 활용하여 재방문을 방지한다.

   (key: 문자열 형태의 노드 값, value: 경로 가중치(=이동 횟수)인 g(n))

4. while문을 사용하여 우선순위 큐가 빌 때까지 현재 빈 퍼즐과 자리를 바꿀 수 있는 숫자의 위치를 바꿔준다.

   만약 HashMap을 통해 이전 방문한 형태라면 건너 뛴다.

5. 현재 노드의 g(n)과 h(n)을 더해서 f(n)을 구한다.

   휴리스틱 값인 h(n)은 잘못 배치된 타일의 수를 세는 것과

   각 블록의 현재 위치와 목표 위치 사이의 Manhattan distance(맨하탄 거리)의 합을 구하는 것 두 가지 방법이 있으나,

   필자는 잘못 배치된 타일의 수를 세는 방법을 채택하였다.

   참고로 빈공간은 제외하고 세야 되기 때문에 빈공간이라고 가정한 문자 #이라면 for문으로 돌아갈 수 있게 continue 키워드를 썼다.

6. 퍼즐의 자리를 바꾸기 전에 우선순위 큐에서 꺼낸 노드의 값이 목표 노드와 같다면 목표 상태에 도달했다는 문구와 함께 최소한의 이동 횟수(=g(n))을 출력한다.

   만약 목표 노드로 도달할 수 없다면 이동 불가 메세지를 출력한다.

시뮬레이션

위에 예시 그림에 목표 노드

123
8#4
765

그리고 시작 노드

283
164
7#5

를 가지고 작성된 소스코드를 실행해보자.

예시에서 시작 노드에서 출발해 가지치기를 시작하게 되면 f(n)이 가장 작은 값을 선택해 또 가지치기를 하며 목표노드로 도달하기 위해 최적의 경로를 도출해내고 있다.

실패 시엔 다음과 같이 콘솔에 출력된다.

출처

[위키백과] A* 알고리즘

[위키백과] 휴리스틱 함수

문제사항

세그먼트 트리의 문제로 골드 1단계이다.

세그먼트 트리에 대한 개념이 부족하다면 아래 포스팅을 참고하길 바란다.

[알고리즘] 세그먼트 트리

단순히 문제를 바라보면 배열 만들어서 최솟값을 구하면 될 것 같지만 이는 시간초과라는 결과가 나온다.

쿼리마다 O(N)의 시간 복잡도를 가지게되어 M개의 쿼리에 대해 이를 반복하면 전체 시간복잡도는 O(N*M)이 되어, N과 M이 큰 경우 시간 초과가 발생한다.

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

public class Main {

    static long[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        arr = new long[N + 1];
        for (int i = 0; i < N; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            sb.append(min(a, b)).append("\n"); // 구간 합 계산 및 결과 저장
        }
        System.out.println(sb);
    }

    public static long min(int start, int end) {
        long minValue = Long.MAX_VALUE;
        for (int i = start - 1; i < end; i++) {
            minValue = Math.min(minValue, arr[i]);
        }
        return minValue;
    }
}

그래서 나온게 세그먼트 트리이다.

여기서 주의할 점은 문제에서 제시한 범위를 보면 int 범위를 초과할 수 있으므로 자료형을 long으로 바꿔주었다.

위의 링크에서도 니와있듯이 N보다 작은 최대의 제곱수의 제곱을 취한 값이 세그먼트 트리의 사이즈라는 사실을 알 수 있다.

즉, 2k >= N인 최소값 k를 구해야 힌다.

양변에 log를 취하면, k >= logN / log2가 된다.

여기서 (logN / log2)의 값을 올림해주었다.

이제, 쉬프트 연산자로 리프노드의 시작 인덱스를 2^k로 만들어주고, 거기에 곱하기 2를 하면 트리 배열의 전체 크기가 나온다.

그리고 문제에서 요구한 a와 b 사이에 최솟값을 구하기 위해 min 메소드를 만들었다.

min 메소드에서는 시작노드나 끝노드가 각각 부모의 오른쪽 자식노드이거나 왼쪽 자식노드라면 최솟값과 비교한 뒤 자신의 부모노드가 아닌 오른쪽에 있는 부모노드, 왼쪽에 있는 부모노드를 택할 수 있도록 만들었다.

다음 코드를 살펴보자.

알고리즘 분류

트리 (세그먼트 트리)

코드

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

public class Main {
    static long[] tree;
    static int N, leafStart;
    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 k = (int) Math.ceil(Math.log(N) / Math.log(2));
        leafStart = 1 << k; // 리프 노드의 시작 인덱스 (2^k)
        int size = 2 * leafStart; // 트리 배열의 전체 크기
        tree = new long[size]; // 트리 배열 초기화

        // 리프 노드에 입력 값 저장
        for (int i = 0; i < N; i++) {
            tree[leafStart + i] = Long.parseLong(br.readLine());
        }

        // 부모 노드들의 값을 자식 노드들의 비교로 최솟값 대입
        for (int i = leafStart - 1; i > 0; i--) {
            tree[i] = Math.min(tree[i * 2], tree[i * 2 + 1]);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            sb.append(min(a, b)).append("\n");
        }
        System.out.println(sb);
    }

    public static long min(int start, int end) {
        start = leafStart + start - 1;
        end = leafStart + end - 1;
        long minValue = Long.MAX_VALUE;

        while (start <= end) {
            if (start % 2 == 1) minValue = Math.min(tree[start++], minValue);
            if (end % 2 == 0) minValue = Math.min(tree[end--], minValue);
            start /= 2;
            end /= 2;
        }

        return minValue;
    }
}

문제사항

세그먼트 트리의 기초적인 문제로 골드 1단계이다.

세그먼트 트리에 대한 개념이 부족하다면 아래 포스팅을 참고하길 바란다.

[알고리즘] 세그먼트 트리

여기서 주의할 점은 문제에서 제시한 범위를 보면 int 범위를 초과할 수 있으므로 자료형을 long으로 바꿔주었다.

위의 링크에서도 니와있듯이 N보다 작은 최대의 제곱수의 제곱을 취한 값이 세그먼트 트리의 사이즈라는 사실을 알 수 있다.

즉, 2k >= N인 최소값 k를 구해야 힌다.

양변에 log를 취하면, k >= logN / log2가 된다.

여기서 (logN / log2)의 값을 올림해주었다.

이제, 쉬프트 연산자로 리프노드의 시작 인덱스를 2^k로 만들어주고, 거기에 곱하기 2를 하면 트리 배열의 전체 크기가 나온다.

그리고 문제에서 요구한 b번째 수를 c로 변경하는 update나 b번째 수부터 c번째 수까지의 합을 구하는 sum을 할 때에는 꼭 요구하는 인덱스는 리프노드 인덱스로 변경해주어야 한다는 점을 잊지 말자.

update는 부모노드에도 영향이 미치기 때문에 이를 고려하여 코드를 구현하였고, sum은 시작노드나 끝노드가 각각 부모의 오른쪽 자식노드이거나 왼쪽 자식노드라면 자신의 부모노드가 아닌 오른쪽에 있는 부모노드, 왼쪽에 있는 부모노드를 택할 수 있도록 만들었다.

다음 코드를 살펴보자.

알고리즘 분류

트리 (세그먼트 트리)

코드

import java.io.*;
import java.util.*;
public class Main {
    static long[] tree; // 세그먼트 트리를 저장할 배열
    static int leafStart; // 리프 노드의 시작 인덱스

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 개수
        int M = Integer.parseInt(st.nextToken()); // 수의 변경이 일어나는 횟수
        int K = Integer.parseInt(st.nextToken()); // 구간의 합을 구하는 횟수

        int k = (int) Math.ceil(Math.log(N) / Math.log(2)); //2^k >= N인 최소값 k
        leafStart = 1 << k; // 리프 노드의 시작 인덱스 (2^k)
        int size = 2 * leafStart; // 트리 배열의 전체 크기
        tree = new long[size]; // 트리 배열 초기화

        // 리프 노드에 입력 값 저장
        for (int i = 0; i < N; i++) {
            tree[leafStart + i] = Long.parseLong(br.readLine());
        }

        // 부모 노드들의 값을 자식 노드들의 합으로 초기화
        for (int i = leafStart - 1; i > 0; i--) {
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M + K; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken()); // 쿼리 타입
            int b = Integer.parseInt(st.nextToken()); // 인덱스 또는 구간 시작
            long c = Long.parseLong(st.nextToken()); // 변경할 값 또는 구간 끝

            if (a == 1) {
                update(b, c); // 값 업데이트
            } else if (a == 2) {
                sb.append(sum(b, (int)c)).append("\n"); // 구간 합 계산 및 결과 저장
            }
        }

        System.out.print(sb);
    }

    // b번째 수를 c로 변경
    public static void update(int index, long value) {
        index = leafStart + index - 1; // 실제 트리 배열에서의 리프노드 인덱스로 변환
        long diff = value - tree[index]; // 변경될 차이 계산
        while (index > 0) {
            tree[index] += diff; // 현재 노드와 모든 부모 노드 업데이트
            index /= 2; // 부모 노드로 이동
        }
    }

    // b번째 수부터 c번째 수까지의 합
    public static long sum(int start, int end) {
        start = leafStart + start - 1; // 시작노드를 실제 트리 배열 인덱스로 변환
        end = leafStart + end - 1; // 끛노드를 실제 트리 배열 인덱스로 변환
        long sum = 0;// 구간 합을 저장할 변수

        while (start <= end) {
            if (start % 2 == 1) sum += tree[start++]; // 시작노드가 오른쪽 자식노드이면 자신의 부모노드가 아닌 오른쪽에 있는 부모노드로 이동 (하단에서 부모로 이동하기 위해 /2)
            if (end % 2 == 0) sum += tree[end--];  // 끝노드가 왼쪽 자식이면 자신의 부모노드가 아닌 왼쪽에 있는 부모노드로 이동 (하단에서 부모로 이동하기 위해 /2)
            start /= 2;
            end /= 2;
        }
        return sum;
    }
}

세그먼트 트리

구간 합과 데이터 업데이트를 빠르게 수행하기 고안해낸 자료구조의 형태 (= 인덱스 트리)를 말한다.

세그먼트 트리 종류

• 구간 합
• 최대 최소 구하기

보통 세그먼트 트리 관련 문제가 나온다면, 구간 합 또는 최대 최소를 구하라는 문제이다.

구현 단계

1. 트리 초기화하기

리프 노드만 원본 데이터 배열을 갖는다.

원본 데이터(=리프 노드)의 부모를 가지는 노드의 값은 앞서 말한대로 구간 합으로 도출된 값이거나 최대 최소로 도출된 값이다,

위 세그먼트 트리를 1차원 배열로 나타내는 작업이 필요하다.

순서대로 알아보자.

• 리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만든다.
• 트리 배열 크기를 구하는 방법은 2^k >=N 을 만족하는 k의 최솟값을 구한 후 2^k*2 를 트리 배열의 크기로 정의하면 된다.

샘플 데이터 {5, 8, 4, 3, 7, 2, 1, 6}

• 위와 같은 샘플 데이터가 있다면 N=8이므로 2^3>=8 이므로 배열의 크기를 2^3*2=16 으로 정의한다.

• 리프노드에 원본 데이터를 입력한다. 이때 리프 노드의 시작위치를 트리 배열의 인덱스로 구해야 하는데, 구하는 방식은 2^k를 시작 인덱스로 취하면된다. 예를 들어 k가 3이면 시작 인덱스는 8이 된다.

• 8번 인덱스부터 리프노드 값들을 순서대로 기입한다.

• 리프 노드를 제외한 나머지 노드 값을 채운다 (2^k-1 부터 1번 쪽으로 채운다.)

• 채워야 하는 인덱스가 N이라고 가정하면 자신의 자식 노드를 이용해 해당 값을 채울 수 있다.

• 자식 노드의 인덱스는 이진 트리 형식이기 때문에 2N, 2N+1이 된다.

• 구간합은 뒤에서부터 탐색

  15/2=7, 7번 인덱스에 15번 인덱스 값인 6을 대입 | 14/2=7, 7번 인덱스에 14번 인덱스 값인 1을 대입 ⇒ 6+1=7 (7번 인덱스 값)

  13/2=6, 6번 인덱스에 13번 인덱스 값인 2를 대입 | 12/2=6, 6번 인덱스에 12번 인덱스 값인 7을 대입 ⇒ 2+7=9 (6번 인덱스 값)

• 최댓값도 뒤에서부터 탐색

  15/2=7, 7번 인덱스에 15번 인덱스 값인 6을 비교 | 14/2=7, 7번 인덱스에 14번 인덱스 값인 1을 비교⇒ max(6,1)=6 (7번 인덱스 값)

  13/2=6, 6번 인덱스에 13번 인덱스 값인 2를 비교 | 12/2=6, 6번 인덱스에 12번 인덱스 값인 7을 비교 ⇒ max(2,7)=7 (6번 인덱스 값)

• 최솟값도 뒤에서부터 탐색

  15/2=7, 7번 인덱스에 15번 인덱스 값인 6을 비교 | 14/2=7, 7번 인덱스에 14번 인덱스 값인 1을 비교⇒ min(6,1)=1 (7번 인덱스 값)

  13/2=6, 6번 인덱스에 13번 인덱스 값인 2를 비교 | 12/2=6, 6번 인덱스에 12번 인덱스 값인 7을 비교 ⇒ min(2,7)=2 (6번 인덱스 값)

• 실제 트리 모양으로 구조화하면 위와 같이 표현된다.

• 구간합 : 특정 구간의 구간합 (2번 인덱스 값이 20인 이유: 4번 인덱스 값+5번 인덱스 값= 8번 인덱스 값+9번 인덱스 값+10번 인덱스 값+11번 인덱스 값)

• 최대: 특정 구간의 최댓값 (2번 인덱스 값이 8인 이유: Max(4번 인덱스 값, 5번 인덱스 값)= Max(8번 인덱스 값, 9번 인덱스 값, 10번 인덱스 값, 11번 인덱스 값)

• 최소: 특정 구간의 최솟값 (2번 인덱스 값이 8인 이유: Min(4번 인덱스 값, 5번 인덱스 값)= Max(8번 인덱스 값, 9번 인덱스 값, 10번 인덱스 값, 11번 인덱스 값)

2. 질의값 구하기

• 주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경

질의 인덱스를 세그먼트 트리 인덱스로 변경하는 방법

세그먼트 트리 index = 주어진 질의 index + 2^k - 1

위 샘플을 예제로 들어 k=3 이라면..

Q. 주어진 질의값이 1~3

A. 1+2^3-1=8 , 3+2^3-1=10 이므로 1에서 3인 질의값을 8에서 10의 질의값으로 변경해준다.

질의값 구하는 과정 (1) start_index % 2 == 1 일 때 해당 노드를 선택 (2) end_index % 2 == 0 일 때 해당 노드를 선택 (3) start_index depth 변경: start_indx = (start_index+1) / 2 연산 실행 //부모 노드 (4) end_index depth 변경: end_index = (end_index-1) / 2 연산 실행 //부모 노드 (5) (1)~(4)과정 반복하다 end_index < start_index가 되면 종료

• (1)~(2)에서 해당 노드를 선택했다는 것은 해당 노드의 부모가 나타내는 범위가 질의 범위를 넘어가기 때문에 해당 노드를 질의값에 영향을 미치는 독립 노드로 선택하고, 해당 노드의 부모 노드는 대상 범위에서 제외한다는 뜻.

  부모 노드를 대상 범위에서 제외하는 방법은 (3)~(4)에서 질의 범위에 해당하는 부모 노드로 이동하기 위해 인덱스 연산을 index/2가 아닌 (index+1)/2, (index-1)/2로 수행하는 것이다.

  질의에 해당하는 노드를 선택하는 방법은 구간 합, 최댓값 구하기, 최솟값 구하기 모두 동일하며 선택된 노드들에 관해 마지막에 연산하는 방식만 다르다.

샘플 데이터 {5, 8, 4, 3, 7, 2, 1, 6}

트리 초기화하기에서 나온 구간 합 샘플을 이용해 2-6번째 구간 합을 구하는 간단한 예제를 살펴보자.

먼저 리프노드의 인덱스로 변경하자.

• start_index=9 end_index=13 인 구간을 구하려고 할때, 8번 인덱스는 구간에 포함되지 않기 때문에 8번 인덱스를 포함하고 있는 부모인 4번 인덱스는 필요하지 않다.

• 실제로 start_index % 2 = 1이기 때문에 위 그림처럼 오른쪽 노드에 위치하고 있다는 것을 알 수 있다. 이는 부모노드를 쓰면 안된다는 뜻이다.

  왜냐하면 해당 구간에 속하지 않는 노드의 값까지 부모노드가 가지고 있기 때문에 부모노드를 쓰면 안된다는 것이다.

• 부모 노드를 대상 범위에서 제외하는 방법은 부모노드 4번 인덱스 대신 바로 옆으로 뛰어 5번 노드로 이동한다. 여기서 도출된 식이 start_index = (start_index+1) / 2 이다.

  (start_index+1)을 하는 이유는 오른쪽에 있는 자식노드였다면 자신의 부모노드가 아닌 오른쪽에 있는 부모노드로 이동해야되기 때문이다.

• 반대로 end_index(=13) % 2 = 1 이므로 부모노드 기준 오른쪽에 있는 자식노드이므로 그대로 자신의 부모노드로 이동한다. 이유는 end_index는 구간에서 마지막 노드이면서, 오른쪽에 위치한 자식노드이므로 부모노드가 자기 자신까지가 포함되어있는 데이터를 가지고 있기 때문이다.

  여기서 도출된 식이 end_indx = (end_index-1) / 2 이다.

end_index < start_index 이므로 종료하고 값을 구한다. 2~6번 구간 합의 값은 선택된 노드의 합인 8+9+7 =24이다.

3. 데이터 업데이트하기

다음은 5번 데이터의 값을 7에서 10으로 업데이트하는 예시이다. 5번 데이터의 인덱스를 리프 노드 인덱스로 변경하면 5+7=12 이므로 12번 노드의 값이 업데이트된다.

트리특성을 살려 이진트리가 부모로 갈 때 나누기 2(/2)를 하며 부모노드로 올라가면서 구간합,최대 최소 값 구하기 등을 진행한다.

문제사항

실버 1단계 문제였다.

이진트리 순회에서 DFS를 활용한 대표적인 문제이며, 전위순회 & 중위순회 & 후위순회 출력을 요구하고 있다.

예전 코딩테스트 입문 시 이진트리 순회에 대해 공부한 적이 있다.

전위순회, 중위순회, 후위순회에 대해 어떻게 접근해야하는지 궁금하다면 다음 포스팅을 참고하자.

[코딩테스트] Recursive, Tree, Graph(DFS, BFS 기초)

전위 순회 (Preorder Traversal): 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리

중위 순회 (Inorder Traversal): 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리

후위 순회 (Postorder Traversal): 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트

알고리즘 분류

이진트리

코드

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

public class Main {
    static Node[] graph;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        graph = new Node[N + 1];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            char parentValue = st.nextToken().charAt(0);
            char leftValue = st.nextToken().charAt(0);
            char rightValue = st.nextToken().charAt(0);

            if (graph[parentValue - 'A'] == null) { // 부모 노드가 생성되지 않은 경우
                graph[parentValue - 'A'] = new Node(parentValue);
            }
            if (leftValue != '.') {// '.'이 아니라면 (부모의 왼쪽 자식 노드가 존재한다면)
                graph[leftValue - 'A'] = new Node(leftValue); // 왼쪽 자식 노드 생성
                graph[parentValue - 'A'].lt = graph[leftValue - 'A']; // 부모 노드와 왼쪽 자식 노드 연결
            }
            if (rightValue != '.') {// '.'이 아니라면 (부모의 오른쪽 자식 노드가 존재한다면)
                graph[rightValue - 'A'] = new Node(rightValue); // 오른쪽 자식 노드 생성
                graph[parentValue - 'A'].rt = graph[rightValue - 'A']; // 부모 노드와 오른쪽 자식 노드 연결
            }
        }

        preorder(graph[0]);
        System.out.println(); //엔터

        inorder(graph[0]);
        System.out.println(); //엔터

        postorder(graph[0]);
        System.out.println(); //엔터
    }

    static class Node {
        char data;
        Node lt, rt; //인스턴스 변수 lt,rt는 Node라는 객체 주소 저장

        public Node(char val) {
            data = val;
            lt = rt = null;
        }
    }

    //전위 순회 (dfs)
    public static void preorder(Node node) {
        if(node ==null) return;
        System.out.print(node.data);
        preorder(node.lt);
        preorder(node.rt);
    }
    //증위 순회 (dfs)
    public static void inorder(Node node) {
        if(node ==null) return;
        inorder(node.lt);
        System.out.print(node.data);
        inorder(node.rt);
    }
    //후위 순회 (dfs)
    public static void postorder(Node node) {
        if(node ==null) return;
        postorder(node.lt);
        postorder(node.rt);
        System.out.print(node.data);
    }
}

문제사항

실버 2단계 문제였다.

앞서 풀었던 [백준] 1068번 트리 (JAVA)와 비슷한 유형이며, 난이도는 더 쉬운 문제이다.

1068번 문제를 풀 때 단뱡향 그래프를 사용하는 방법과 양방향 그래프를 사용하는 방법 두 가지 방법으로 나눠 풀었었다.

트리의 부모 찾기 문제도 부모를 찾기 위해서는 양방향 그래프로 접근해야 한다.

예제 입력 1을 그래프로 표현해보면

위와 같은 트리로 나타낼 수 있고, 출력은 2의 부모 4, 3의 부모 6, 4의 부모 1, 5의 부모 3, 6의 부모 1, 7의 부모 4 이므로 "4 6 1 3 1 4" 가 출력된다.

알고리즘 분류

트리, DFS

코드

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

public class Main {
    static ArrayList<Integer>[] graph;
    static int[] parent;
    static boolean[] visited;
    static int N, answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        graph = new ArrayList[N + 1];
        parent = new int[N + 1];
        visited = new boolean[N + 1];

        for (int i = 0; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < N-1; i++) { 
        //트리에서 간선의 수는 항상 노드의 수보다 1 적다
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }
        DFS(1);

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i < parent.length; i++) {
            sb.append(parent[i]).append("\n");
        }
        System.out.println(sb);
    }


    static void DFS(int v) {
        visited[v] = true;
        for (int current : graph[v]) {
            if (!visited[current]) {
                parent[current] = v;
                DFS(current);
            }
        }
    }
}

문제사항

골드 5단계 문제였다.

트리 문제에서 그래프로 푸는 Tree 문제이고, DFS(깊이 우선 탐색)로 풀어야 하는 유형이다.

문제에서 원하는건 트리에서 특정 노드를 제거하였을 때 리프노드의 개수를 출력하면 된다.

문제에 대해 설명하기 전에 리프노드와 같은 트리 관련 구성요소와 트리문제는 어떻게 접근해야되는지 부터 알아보자.

트리 알아보기

트리는 노드와 에지로 연결된 그래프의 특수한 형태 = 그래프의 표현으로도 tree를 표현할 수 있다.

특징

• 순환 구조 X, 필수로 1개의 루트 노드 존재

• 루트 노드 제외한 노드는 단 1개의 부모 노드 가진다.
• 트리의 부분 트리 역시 트리의 모든 특징을 따른다.

⇒ 트리에서 임의의 두 노드를 이어주는 경로는 유일하다.

트리의 핵심 이론

• 트리의 구성 요소

문제에서 말한 리프 노드는 표에서 말하듯 트리에서 가장 하위에 존재하는 노드이다.

Tip) 코딩테스트에서 Tree

(1) 그래프로 푸는 Tree - Node Edge : 인접리스트로 표현 ⇒ “DFS”, “BFS”

(2) Tree만을 위한 문제 - 이진 트리 (난이도 : 중) - 세그먼트 트리 (index tree) (난이도 : 상) - LCA (최소공통조상) (난이도 : 상)

세그먼트 트리 : 1차원 배열로 tree 표현 ex) 5/2 = 2 : E의 부모는 B 3/2 = 1 : C의 부모는 A

자식으로 이동할 때는 index x 2 혹은 index x 2 +1

다시 한번 말하자면 위 문제는 트리에서 노드를 하나 제거한 후 남은 리프 노드의 개수를 구하는 문제이다. DFS(깊이 우선 탐색)를 사용하여 효율적으로 해결할 수 있다.

알고리즘 분류

트리, DFS

코드

두 가지 방법으로 푸었다.

먼저 첫 번째 풀이의 특징을 살펴보자.

1. 부모에서 자식으로의 단방향 그래프를 사용하였다.

2. 그래프에서 삭제할 노드를 직접 제거하였다. (루트가 삭제 대상일 경우 DFS 수행 X)

3. 리프 노드 수를 자식에서 부모로 누적하여 계산하였다.

4. 각 노드의 서브트리에 있는 리프 노드 수를 배열에 저장하였다.

첫 번째 방법은 트리의 구조에 초점을 맞춰 풀었기 때문에 일반적인 그래프 탐색과 거리가 멀다.

코드 1

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

public class Main {
    static ArrayList<Integer>[] graph;
    static int[] leaf;
    static int N, target, root; // N: 노드 개수, target: 삭제할 노드, root: 루트 노드

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

        N = Integer.parseInt(br.readLine()); //N은 50보다 작거나 같은 자연수
        leaf = new int[N];
        graph = new ArrayList[N + 1]; //인접리스트 초기화 (리스트의 배열(또는 리스트의 리스트))

        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<>();
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int parent = Integer.parseInt(st.nextToken());
            if (parent == -1) {
                root = i;
            } else {
                graph[parent].add(i); // 부모 노드에 자식 노드 추가
            }
        }
        target = Integer.parseInt(br.readLine()); //지울 노드의 번호

        for (int i = 0; i < N; i++) {
            graph[i].removeIf(integer -> integer == target); // 삭제할 노드를 자식으로 가진 노드에서 제거
            //그래프 속 지울 노드의 번호 삭제
        }
        if(target != root) DFS(root, -1);// 루트가 삭제 대상이 아닐 경우에만 DFS 수행

        System.out.println(leaf[root]);
    }

    static void DFS(int v, int parent) {
        if(graph[v].isEmpty()) leaf[v] = 1; //자식이 없다면 그 노드는 리프 노드

        for (int child : graph[v]) {
            DFS(child,v);
            leaf[v] += leaf[child];// 자식 노드의 리프 노드 개수를 현재 노드에 더함
        }
    }

}

예제 입력 1 (N=5, 부모 노드 = [-1 0 0 1 1], target=2)의 경우 출력이 어떻게 2가 나오는지 살펴보자.

(1) 트리의 구성

• 0이 루트 노드
• 0의 자식: 1, 2
• 1의 자식: 3, 4

(2) 노드 2 삭제:

• grape[0]에서 2 제거

(3) DFS 수행:

• 0 방문: 자식 1
• 1 방문: 자식 3, 4
• 3 방문: 리프 노드 (leaf[3] = 1)
• 4 방문: 리프 노드 (leaf[4] = 1)
• 1로 돌아옴: leaf[1] = leaf[3] + leaf[4] = 2
• 0으로 돌아옴: leaf[0] = leaf[1] = 2

(4) 결과: 2 (리프 노드 개수)

다음으로 두 번째 풀이의 특징을 살펴보자.

1. 부모와 자식 간의 양방향 그래프를 사용하였다.

2. 삭제할 노드를 방문하지 않는 방식으로 처리하였다.

3. 루트가 삭제 대상일 경우 즉시 0을 출력하고 종료한다.

4. 전역 변수로 리프 노드 수를 직접 카운트한다.

두 번째 방법은 일반적인 그래프 탐색에 가깝기 때문에, 여러 유형에 쉽게 접근할 수 있다.

코드 2

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

public class Example1068_2 {
    static ArrayList<Integer>[] graph;
    static int[] parent;
    static boolean[] visited;
    static int N, target, answer; // N: 노드 개수, target: 삭제할 노드, root: 루트 노드

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

        N = Integer.parseInt(br.readLine()); //N은 50보다 작거나 같은 자연수
        graph = new ArrayList[N + 1]; //인접리스트 초기화 (리스트의 배열(또는 리스트의 리스트))
        parent = new int[N + 1];
        visited = new boolean[N + 1];

        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<>();
        }

        int root = -1;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int parent = Integer.parseInt(st.nextToken());
            if (parent == -1) {
                root = i;
            } else {
                graph[i].add(parent);
                graph[parent].add(i); // 서로 연결
            }
        }
        target = Integer.parseInt(br.readLine()); //지울 노드의 번호

        if (target == root) {
            System.out.println(0);
            return;
        } else {
            DFS(root);
        }
        System.out.println(answer);
    }

    static void DFS(int v) {
        visited[v] = true;

        int children = 0;
        for (int current : graph[v]) {
            if (current != target && !visited[current]) {
                children++;
                DFS(current);
            }
        }
        if (children == 0) {
            answer++; //자식노드가 없므면 리프노드
        }
    }

}

문제사항

실버 1단계 문제였다.

[백준] 1219번 오민식의 고민 (JAVA) 문제와 마찬가지로 플로이드-워셜 문제이다.

플로이드-워셜 알고리즘에 대해 궁금하다면 위 포스팅을 참고하자.

여기서 주의해야할 점은 각 노드(유저) 사이의 최단 거리가 담긴 D 배열을 이용해 케빈 베이컨의 최소 개수에 해당하는 인덱스를 찾아 출력하면 된다.

알고리즘 분류

그래프 (플로이드-워셜)

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] D = new int[N + 1][N + 1];
        int cost_max = 50000;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    D[i][j] = 1;
                } else {
                    D[i][j] = cost_max;
                }
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            // 양방향 설계 (a->b, b->a)
            D[A][B] = D[B][A] = 1;
        }

        //플로이드 워셜
        for (int K = 1; K <= N; K++) {
            for (int S = 1; S <= N; S++) {
                for (int E = 1; E <= N; E++) {
                    D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]);
                }
            }
        }

        int index = 0;
        int res = cost_max;
        // 가장 적은 값을 가진 인덱스 출력
        for (int i = 1; i <= N; i++) {
            int value = 0; // i=1, i=2, i=2.. 각 유저로 취급
            for (int j = 1; j <= N; j++) {
                value += D[i][j]; // 유저의 케빈 베이컨 수
            }

            if (res > value) {
                res = value;
                index = i;
            }
        }

        System.out.println(index);
    }
}

문제사항

실버 1단계 문제였다.

[백준] 1219번 오민식의 고민 (JAVA) 문제와 마찬가지로 플로이드-워셜 문제이다.

플로이드-워셜 알고리즘에 대해 궁금하다면 위 포스팅을 참고하자.

플로이드-워셜의 핵심이론은 다음과 같다.

A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로이다.

가만보면 위 문제에서 i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. 라고 언급하고 있다.

문제에서는 i에서 j로 갈 수 있는 경로가 있는지 판단해 인접행렬로 출력을 요구하고 있다.

이는 플로이드 핵심원리와 똑같다는 것을 간접적으로 말하고 있다.

따라서 거쳐가는 정점이 k라고 할때 D[i][k] == 1 그리고 D[k][i] == 1이라는 두 조건 모두 부합하다면 D[i][j] = 1 이라고 할 수 있다.

알고리즘 분류

그래프 (플로이드-워셜)

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[][] D = new int[N + 1][N + 1];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                D[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //플로이드-워셜
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (D[i][k] == 1 && D[k][j] == 1) {
                        D[i][j] = 1;
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(D[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

문제사항

골드 4단계 문제였다.

문제를 보면 이 역시도 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 문제이다.

앞전에 다익스트라 알고리즘과 벨만포드 알고리즘과 다른 점은 모든 도시의 쌍 (A, B)에 대해서 구해야한다는 점이다.

즉, 특점 시작점이 없고, 임의의 모든 노드의 쌍의 최단거리를 구해야 한다.

이 때는 플로이드-워셜 알고리즘을 사용해야 한다.

'플로이드-워셜' 란?

그래프에서 최단 거리를 구하는 알고리즘은 다익스트라, 벨만포드, 플로이드 워셜이 있다.

플로이드-워셜은 모든 노드 간에 최단경로 탐색을 요구한다.

특징은 벨만포드와 마찬가지로 음수 가중치 에지가 있어도 수행 가능하다는 점이다.

또한 동적 계획법 원리를 이용해 알고리즘 접근해야한다.

시간복잡도는 특이하게 O(V^3) 를 가진다. (노드수 : V)

다른 알고리즘에 비해 꽤 느린 시간복잡도를 가지고 있기 때문에 값의 범위를 잘 살펴보아야 한다.

만약 N이 시간복잡도를 신경써야할 만큼의 큰 수가 주어진다면 플로이드-워셜을 사용하면 안된다.

N의 크기가 100, 200 정도의 작은 수로 주어졌을 때 사용 가능하다.

플로이드-워셜의 핵심이론

A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로이다.

색칠된 에지 경로가 1 → 5 최단 경로라면 1 → 4 최단 경로와 4 → 5 최단 경로 역시 색칠된 에지로 이뤄질 수 밖에 없다.

도출한 플로이드-워셜 점화식

D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

K는 S와 E 사이에 있는 모든 노드를 거쳐갔을 때 가장 최적 값을 K에 넣어준다.

1. 리스트를 선언하고 초기화하기

• S와 E의 값이 같은 칸은 0, 다른 칸은 무한대로 초기화한다.

• S==E는 자기 자신에게 가는 데 걸리는 최단 경로값을 의미하기 때문이다.

2. 최단 거리 리스트에 그래프 데이터 저장하기

• 출발 노드 S, 도착노드 E, 에지 가중치 W라고 했을 때 D[S][E] = W 에지 정보 리스트에 입력한다.

• “인접 행렬” 로 표현

3. 점화식으로 리스트 업데이트하기

• 기존에 구했던 점화식을 3중 for문 형태로 반복해 리스트 값 업데이트

• 완성된 리스트는 모든 노드 간의 최단 거리를 알려준다.

• 예를 들어 1번 노드에서 5번까지 가는 최단 거리는 D[1][5]=6으로 나타난다는 것을 알 수 있다.

• 플로이드-워셜 알고리즘은 모든 노드 간의 최단 거리를 확인해 주기 때문에 시간 복잡도가 O(V^3)으로 빠르지 않은 편이다.

  • 따라서 노드 개수 범위가 다른 그래프에 비해 적게 나타나는 것을 알 수 있다.

알고리즘 분류

그래프 (플로이드-워셜)

코드

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

public class Main
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int[][] D = new int[N + 1][N + 1];

        // INF 값을 100,000,000으로 설정 (최대 비용 100,000 * 최대 도시 수 100)
        final int max_cost = 100000000;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    D[i][j] = 0;
                } else {
                    D[i][j] = max_cost;
                }
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            // ex> "1 4 1"과 "1 4 2"가 입력으로 들어왔으면, "1 4 1"을 택해야 함.
            D[a][b] = Math.min(D[a][b], c);
        }

        //플로이드-워셜
        for (int K = 1; K <= N; K++) {
            for (int S = 1; S <= N; S++) {
                for (int E = 1; E <= N; E++) {
                    D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (D[i][j] == max_cost) {
                    D[i][j] = 0;
                }
                sb.append(D[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}

문제사항

플래티넘 5단계 문제였다.

일반적인 벨만-포드는 N-1까지 최단 경로를 업데이트 한 뒤 마지막으로 한번 반복하여 사이클 여부를 여부를 판단한다.

하지만 이 문제에서는 오민식이 벌 수 있는 돈이 무한대 라고 언급한다.

이는 양의 사이클이 발생하며 (=최대 거리를 구하며) 양의 사이클인지 음의 사이클인지 판단하라는 뜻이다.

계속해서 벨만-포드 문제를 풀며 최단 경로를 업데이트 했으나, 여기선 최대 거리를 구해야 한다.

키 포인트

• 각 도시에서 돈을 벌 수 있다.
• 도시 간 이동에는 비용이 든다.
• 같은 도시를 여러 번 방문 가능하다.
• 양의 사이클 (=계속 돈을 벌 수 있는 루트)이 존재할 수 있다.

자료구조

• Edge[]: 각 교통 수단(간선)의 정보를 저장
• long[] dist: 각 도시까지의 최대 이익을 저장
• long[] money: 각 도시에서 벌 수 있는 돈을 저장

** int 범위를 넘을 수 있으므로 long을 사용

벨만-포드 알고리즘 변형

• 초기에 모든 도시의 이익을 최소값으로 설정
• N+50번 반복하여 각 간선을 확인하고 이익을 갱신 => 최댓값인 N+50번 정도의 충분한 반복으로 모든 가능한 경로를 고려
• 양의 사이클 검출: N번 이상 반복 후에도 이익이 증가하면 무한대로 설정

알고리즘 분류

그래프 (벨만 포드)

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());  // 도시의 수
        int start = Integer.parseInt(st.nextToken());  // 시작 도시
        int destination = Integer.parseInt(st.nextToken());  // 도착 도시
        int M = Integer.parseInt(st.nextToken());  // 교통 수단의 개수

        Edge[] grape = new Edge[M + 1];  // 교통 수단(간선) 정보를 저장할 배열
        long[] dist = new long[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());  // 도착 도시
            int c = Integer.parseInt(st.nextToken());  // 교통 비용
            grape[i] = new Edge(a, b, c);
        }

        // 각 도시에서 벌 수 있는 돈 입력
        long[] money = new long[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            money[i] = Integer.parseInt(st.nextToken());
        }

        // 벨만 포드 알고리즘 시작
        Arrays.fill(dist, Long.MIN_VALUE);  // 모든 도시의 초기 수익을 최소값으로 설정
        dist[start] = money[start];  // 시작 도시의 수익 초기화

        // N+50번 반복 (양의 사이클 검출을 위해 충분히 큰 횟수로 설정)
        for (int i = 0; i <= N + 50; i++) {
            for (int j = 0; j < M; j++) {
                Edge now = grape[j];
                // 출발 도시에 도달할 수 없는 경우 스킵
                if (dist[now.st] == Long.MIN_VALUE) {
                    continue;
                }
                // 출발 도시가 양의 사이클에 포함된 경우, 도착 도시도 무한대 수익으로 설정
                else if (dist[now.st] == Long.MAX_VALUE) {
                    dist[now.end] = Long.MAX_VALUE;
                }
                // 수익이 증가하는 경우 업데이트
                else if (dist[now.end] < dist[now.st] + money[now.end] - now.cost) {
                    dist[now.end] = dist[now.st] + money[now.end] - now.cost;
                    // N번 이상 반복했을 때 여전히 업데이트가 발생하면 양의 사이클로 판단
                    if (i >= N) {
                        dist[now.end] = Long.MAX_VALUE;
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        // 도착 도시에 도달할 수 없는 경우
        if (dist[destination] == Long.MIN_VALUE) {
            sb.append("gg").append("\n");
        }
        // 도착 도시가 양의 사이클에 포함된 경우
        else if (dist[destination] == Long.MAX_VALUE) {
            sb.append("Gee").append("\n");
        }
        // 정상적으로 도착 도시에 도달한 경우
        else {
            sb.append(dist[destination]).append("\n");
        }
        System.out.println(sb);
    }

    // 간선(교통 수단) 정보를 저장하는 클래스
    static class Edge{
        int st;  // 출발 도시
        int end;  // 도착 도시
        int cost;  // 비용

        public Edge(int st, int end, int cost) {
            this.st = st;
            this.end = end;
            this.cost = cost;
        }
    }
}

문제사항

골드 4단계 문제였다.

문제를 읽어보면 1번도시부터 N번 도시로 가는 가장 빠른 시간을 구해야 하며, 여기선 도시 간 이동하는데 있어 가중치가 있다.

시작 도시(노드)가 주어지고, 음의 가중치를 가진 엣지가 존재한다.

위 문제는 음수 사이클까지 판단해야되기 때문에 벨만-포드 알고리즘을 사용해야 한다.

그렇다면 벨만-포드 알고리즘이 무엇인지 알아보자.

'벨만-포드' 란?

그래프에서 최단 거리를 구하는 알고리즘은 다익스트라, 벨만포드, 플로이드 워셜이 있다.

다익스트라는 직전 포스팅에서 이론을 학습하고, 총 3개의 백준 문제를 풀었었다. 다익스트라가 무슨 알고리즘이고, 어떤 유형으로 출제되는지 궁금하다면 다음 포스팅을 참고하자.

[백준] 1753번 최단경로(JAVA)

벨만-포드는 특정 출발 노드(=시작점 존재)에서 다른 모든 노드의 최단 경로 탐색을 요구한다.

여기서 특징은 음수 간선이 존재하여, 음수 사이클의 존재 여부를 판단할 수 있다.

이때 시간 복잡도는 O(VE)이다.

1. ”에지 리스트” 로 그래프를 구현하고 최단 경로 리스트 초기화

에지를 중심으로 동작함으로 그래프를 에지 리스트로 구현한다.

최단 경로 리스트는 출발노드는 0, 나머지 노드는 무한대로 초기화한다.

2. 모든 에지를 확인해 정답 리스트 업데이트하기

업데이트 반복 횟수는 노드 개수 -1이다.

노드의 개수가 N, 음수 사이클이 없다면 특정 두 노드의 최단거리를 구성할 수 있는 에지의 최대 개수는 N-1이기 때문이다.

모든 에지 E = ( s, e, w )에서 다음 조건을 만족하면 새 업데이트를 실행한다.

[업데이트 조건과 방법]

D[s] != 무한대이며 D[s] + w < D[e]일 때 D[e] = D[s] + w로 리스트 값 업데이트

업데이트 반복 횟수가 K번이면, 해당 시점에 정답 리스트의 값은 시작점에서 K개의 에지를 사용했을 때 각 노드에 대한 최단 거리를 구할 수 있다.

• 처음에는 모든 에지를 다 검토
• 이때 출발 노드(=1)는 무한대가 아니여야 한다.

[ 시작 노드에서 1개의 에지를 사용 ]

• 1에서 2로 가는데 가중치 8이 있다.
• D[1] + 8 < D[2]
• 0+8<무한대 이므로 새로 들어온 D[1]+8이 더 작다.
• 따라서 더 작은 값을 D[2]에 대입해준다.

• 이처럼 업데이트를 시작할 수 있는 노드는 1밖에 없다.

• 그러므로 1에서 3으로 이동하는 에지도 업데이트 시킬 수 있다.

[ 시작 노드에서 2개의 에지를 사용 ]

• 에지 4,5는 이미 무한대기 때문에 조건에서 제외됨

• D[2] + 5 < D[5] 조건에 부합하므로 D[5]는 8+5=13을 대입

• D[3] + 7 < D[4] 조건에 부합하므로 D[4]는 3+7=10을 대입

[ 노드의 개수가 5개므로 4번까지 업데이트를 반복 ⇒ 최단거리 완성 ]

그러나..

벨만포드는 음수 사이클이 있는지 찾는 문제가 많이 나온다!

• 음수 사이클이 없을때 N-1번 에지 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단 거리를 알려 주는 정답 리스트가 완성

⇒ 마지막으로 이 그래프에 음수 사이클이 존재하는지 확인

3. 음수 사이클 유무 확인하기

• 모든 에지를 한 번씩 다시 사용해 업데이트 되는 노드가 발생하는지 확인
• 만약 업데이트 되는 노드가 있다면 음수 사이클이 있다는 뜻
• 음수 사이클 존재하면 이 사이클을 무한하게 돌수록 가중치가 계속 감소하여 최단거리 구할 수 없음

• D[5]-2 < D[4]를 계산해보면 11-2< 10이기 때문에 업데이트 조건에 부합한다.

• N-1번을 사용해서 최단거리가 나왔는데 한번 더 했을 때 업데이트가 되었다는 것은 “음수 사이틀이 있다는 뜻”

  ⇒ 해당 그래프는 최단 거리를 구할 수 없는 그래프이다.

알고리즘 분류

그래프 (벨만-포드 알고리즘)

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 에지리스트
        Edge[] edges = new Edge[M + 1];
        // 정답배열(최단거리 배열)
        long[] D = new long[N + 1];
        Arrays.fill(D, Integer.MAX_VALUE);//dist 배열의 모든 요소를 Integer.MAX_VALUE로 초기화

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(A, B, C);
        }

        // 벨만 포드
        D[1] = 0; // 시작노드는 0
        for (int i = 1; i < N; i++) { // 업데이트 반복 횟수: N-1
            for (int j = 0; j < M; j++) {
                Edge edge = edges[j];
                if (D[edge.start] != Integer.MAX_VALUE && D[edge.start] + edge.cost < D[edge.end]) {
                    D[edge.end] = D[edge.start] + edge.cost; // 업데이트
                }
            }
        }

        // 음수 사이클 판별 ( 한번 더 수행 )
        boolean check = false;
        for (int i = 0; i < M; i++) {
            Edge edge = edges[i];
            if(D[edge.start] != Integer.MAX_VALUE && D[edge.start] + edge.cost < D[edge.end]){
                check = true;
            }
        }

        StringBuilder sb = new StringBuilder();
        if (check) { //음수 사이클이 존재한다면
            sb.append("-1");
        } else { //음수 사이클이 존재하지 않다면
            //D[1]은 0이므로 2부터 시작
            for (int i = 2; i <= N; i++) {
                if (D[i] == Integer.MAX_VALUE) {
                    sb.append("-1").append("\n");
                } else {
                    sb.append(D[i]).append("\n");
                }
            }
        }
        System.out.println(sb);
    }

    static class Edge {
        int start;
        int end;
        int cost;

        public Edge(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
    }
}

출처

[백준 11657] 타임머신 (JAVA)

직전 포스팅 : [재능교환소] Spring Boot로 Stomp 기반 1:1 채팅 구현 (with React)

프로젝트를 개발하는 과정에서 실시간 소통을 위한 1:1채팅 기능이 필요하여 만들었었다.

초기에는 빠른 구현과 간단한 설정을 위해 Spring Boot의 내장 메시지 브로커를 활용하여 STOMP 프로토콜 기반의 1:1 실시간 채팅 시스템을 구현했다.

이 방식은 별도의 외부 메시징 시스템 없이 채팅 기능을 구현할 수 있어 개발 초기 단계에 적합했다.

하지만 시스템의 확장성과 안정성에 대한 문제가 남아있었다.

특히 Nginx를 사용한 무중단 배포를 구현하려 했을 때, Spring Boot의 내장 브로커로는 배포 과정에서의 메시지 연속성 보장에 한계가 있었다.

내장 브로커는 단일 서버 환경에서는 잘 작동하지만, 무중단 배포 과정에서 메시지의 일관성을 보장하기 어렵다.

이러한 문제를 해결하고 시스템의 안정성을 개선하기 위해 *외부 메시지 브로커인 *RabbitMQ를 도입하기로 결정했다.

🍫 RabbitMQ에 대해 알아보자

1. Producer:

• 메시지를 생성하고 RabbitMQ로 보내는 주체이다.
• 메시지를 Exchange에 발행(publish)한다.
• 메시지 생성 후 어떤 Exchange로 보낼지 결정한다.

2. Exchange:

• Producer로부터 받은 메시지를 Queue로 라우팅하는 역할을 한다.
• 여러 타입의 Exchange가 있으며, 각각 다른 라우팅 로직을 가진다. (Direct, Fanout, Topic, Headers).
• 메시지의 라우팅 키와 Exchange에 설정된 규칙에 따라 하나 이상의 Queue로 메시지를 전달한다.

3. Queue:

• 메시지가 저장되는 버퍼이다.
• Consumer가 메시지를 받아갈 때까지 메시지를 보관한다.
• 하나의 Queue에 여러 Consumer가 연결될 수 있으며, 이 경우 라운드 로빈 방식으로 메시지를 분배한다.
• Exchange와 바인딩(binding)되어 있어, 특정 조건의 메시지만 받을 수 있다.

4. Consumer:

• Queue로부터 메시지를 받아 처리하는 응용 프로그램이다.
• 하나 이상의 Queue를 구독(subscribe)하여 메시지를 소비한다.
• 메시지를 받은 후 처리하고, 처리 완료를 RabbitMQ에 알린다 (ack).

작동과정

1. Producer가 메시지를 생성하여 Exchange에 발행
2. Exchange는 라우팅 규칙에 따라 메시지를 적절한 Queue(들)로 전달
3. 메시지는 Consumer가 가져갈 때까지 Queue에 저장
4. Consumer는 구독 중인 Queue에서 메시지를 받아 처리

앞서 말했듯 RabbitMQ에서는 메시지를 다양한 방식으로 라우팅하기 위해 네 가지 타입의 Exchange를 제공한다.

각 Exchange 타입의 특징과 작동 원리를 살펴보자.

🍡 Exchange 타입

RabbitMQ Direct Exchange

Direct Exchange는 메시지의 라우팅 키와 동일한 바인딩 키를 가진 큐에 메시지를 전달한다.

작동 과정:

1. Producer가 메시지를 Direct Exchange에 전송한다.
2. Exchange는 메시지의 라우팅 키를 확인한다.
3. Exchange는 자신에게 바인딩된 큐들 중 바인딩 키가 메시지의 라우팅 키와 정확히 일치하는 큐를 찾는다.
4. 일치하는 큐에 메시지를 전달한다.

RabbitMQ Fanout Exchange

Fanout Exchange는 자신에게 바인딩된 모든 큐에 메시지를 라우팅한다. 라우팅 키는 무시된다.

작동 과정:

1. Producer가 메시지를 Fanout Exchange에 전송한다.
2. Exchange는 자신에게 바인딩된 모든 큐를 확인한다.
3. 바인딩된 모든 큐에 메시지의 복사본을 전송한다.

RabbitMQ Topic Exchange

Topic Exchange는 라우팅 키와 바인딩 패턴 사이의 와일드카드(*) 매칭을 통해 메시지를 큐에 전달한다.

작동 과정:

1. Producer가 메시지를 Topic Exchange에 전송한다.
2. Exchange는 메시지의 라우팅 키를 확인한다.
3. Exchange는 자신에게 바인딩된 큐들의 바인딩 패턴과 메시지의 라우팅 키를 비교한다.
4. 매칭되는 패턴을 가진 모든 큐에 메시지를 전달한다.

RabbitMQ Headers Exchange

Headers Exchange는 메시지의 헤더 속성을 사용하여 라우팅을 수행한다.

작동 과정:

1. Producer가 메시지를 Headers Exchange에 전송한다.
2. Exchange는 메시지의 헤더를 확인한다.
3. Exchange는 자신에게 바인딩된 큐들의 바인딩 속성과 메시지의 헤더를 비교한다.
4. 매칭되는 속성을 가진 큐에 메시지를 전달한다.

설치

윈도우 pc 로컬에 설치한다면 다음 링크를 참고하길 바란다.

Windows10에 RabbitMQ 빠르게 설치하기 (with Erlang)

🍮 RabbitMQ를 사용한 1:1 채팅 구현

필자는 Maven을 사용하였기 때문에 pom.xml에 의존성을 추가해주었다.

pom.xml

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-amqp</artifactId>
</dependency>

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-reactor-netty</artifactId>
    <version>3.0.0</version>
</dependency>

RabbitMQ 의 정상적인 동작을 위해 설정 클래스 만들어 보자.

RabbitConfig

@Configuration
@EnableRabbit
@RequiredArgsConstructor
public class RabbitConfig {

    private static final String CHAT_QUEUE_NAME = "chat.queue";
    private static final String CHAT_EXCHANGE_NAME = "chat.exchange";
    private static final String ROUTING_KEY = "*.room.*";

    //Queue 등록
    @Bean
    public Queue queue() {
        return new Queue(CHAT_QUEUE_NAME, true);
    }

    //Exchange 등록
    @Bean
    public TopicExchange exchange() {
        return new TopicExchange(CHAT_EXCHANGE_NAME);
    }

    // Exchange와 Queue바인딩
    @Bean
    public Binding binding(Queue queue, TopicExchange exchange){
        return BindingBuilder
                .bind(queue)
                .to(exchange)
                .with(ROUTING_KEY);
    }

    // RabbitMQ와의 메시지 통신을 담당하는 클래스
    @Bean
    public RabbitTemplate rabbitTemplate() {
        RabbitTemplate rabbitTemplate = new RabbitTemplate(connectionFactory());
        rabbitTemplate.setMessageConverter(jsonMessageConverter());
        return rabbitTemplate;
    }

    // RabbitMQ와의 연결을 관리하는 클래스
    @Bean
    public ConnectionFactory connectionFactory() {
        CachingConnectionFactory factory = new CachingConnectionFactory();
        factory.setHost("localhost");
        factory.setPort(5672);
        factory.setVirtualHost("/");
        factory.setUsername("guest");
        factory.setPassword("guest");
        return factory;
    }

    // 메시지를 JSON형식으로 직렬화하고 역직렬화하는데 사용되는 변환기
    // RabbitMQ 메시지를 JSON형식으로 보내고 받을 수 있음
    @Bean
    public Jackson2JsonMessageConverter jsonMessageConverter() {
        //LocalDateTime serializable을 위해
        ObjectMapper objectMapper = new ObjectMapper();
        objectMapper.configure(SerializationFeature.WRITE_DATES_AS_TIMESTAMPS, true);
        objectMapper.registerModule(dateTimeModule());

        Jackson2JsonMessageConverter converter = new Jackson2JsonMessageConverter(objectMapper);

        return converter;
    }

    @Bean
    public Module dateTimeModule() {
        return new JavaTimeModule();
    }
}

위 설정 내용을 살펴보면 다음과 같다.

• chat.queue라는 이름의 Queue 를 생성
• chat.exchange라는 이름의 Topic Exchange를 생성
• Queue와 Exchange를 *.room.* 라우팅 키로 Binding
• JSON형태로 주고받을 수 있도록 RabbitTemplate 설정
• RabbitMQ 서버와의 연결을 관리하는 ConnectionFactory를 설정
• 로컬호스트의 5672 포트로 연결하며, 기본 사용자 이름과 비밀번호인 guest를 사용
• Jackson 라이브러리를 사용하여 메시지를 JSON 형식으로 직렬화/역직렬화
• LocalDateTime 등의 날짜/시간 타입을 처리하기 위한 설정

여기서 주의 깊게 봐야되는 점은 Exchange 타입 중 Topic Exchange을 사용했다는 점이다.

특정 패턴의 라우팅 키에 따라 메세지를 라우팅 할 수 있는데, 여기서 특정 패턴을 방 번호ID로 주었다.

(채팅방 생성 시, UUID로 고유한 방 번호를 생성하여 채팅방 ID로 사용한다. 이 ID와 함께 채팅방에 참여한 사용자들의 userId를 데이터베이스에 저장하고 있다.)

기존에 만들었던 WebSocketConfig도 수정해주어야 한다.

WebSocketConfig

@Configuration
@EnableWebSocketMessageBroker
@RequiredArgsConstructor
public class WebSocketConfig implements WebSocketMessageBrokerConfigurer {

    @Override
    public void registerStompEndpoints(StompEndpointRegistry registry) {

        // socketJs 클라이언트가 WebSocket 핸드셰이크를 하기 위해 연결할 endpoint를 지정할 수 있다.
        registry.addEndpoint("/chat/inbox")
                .setAllowedOriginPatterns("*"); // cors 허용을 위해 꼭 설정해주어야 함. setCredential() 설정시에 AllowedOrigin 과 같이 사용될 경우 오류가 날 수 있으므로 OriginPatterns 설정으로 사용하였음
    }

    @Override
    public void configureMessageBroker(MessageBrokerRegistry registry) {

        // 메시지 브로커 설정
        registry.setPathMatcher(new AntPathMatcher(".")); // url을 chat/room/3 -> chat.room.3으로 참조하기 위한 설정
        registry.enableStompBrokerRelay("/queue", "/topic", "/exchange", "/amq/queue")
                .setRelayHost("localhost")
                .setRelayPort(61613)
                .setSystemLogin("guest")
                .setSystemPasscode("guest")
                .setClientLogin("guest")
                .setClientPasscode("guest");

        // 클라이언트로부터 메시지를 받을 api의 prefix를 설정함
        // publish
        registry.setApplicationDestinationPrefixes("/pub");


    }


}

보면 나머지는 다 동일하나, configureMessageBroker()에 메시지 브로커 설정이 변경되었다.

메시지 브로커 설정

이전에는 registry.enableSimpleBroker("/sub")로 적어 내장 메모리 기반 브로커를 사용하였다.

이를 registry.enableStompBrokerRelay(...)로 작성해주며 RabbitMQ와 같은 외부 메시지 브로커 사용할 수 있도록 변경해주었다.

registry.setPathMatcher(new AntPathMatcher("."))은 URL 패턴을 점(.)으로 구분하도록 설정한 것이다.

브로커 릴레이 호스트를 localhost, RabbitMQ의 STOMP 프로토콜 기본 포트인 61613으로 설정해주었다.

이후 setSystemLogin("guest") 와 setSystemPasscode("guest")은 STOMP 브로커 릴레이가 RabbitMQ 서버에 연결할 때 사용하는 시스템 레벨의 인증 정보를 추가해준 것

setClientLogin("guest") 와 setClientPasscode("guest")는 개별 클라이언트 연결에 사용되는 인증 정보를 추가해주었다.

다음은 채팅 메시지를 처리하는 컨트롤러 및 서비스를 수정해보자.

ChatMessageController

@Controller
@RequiredArgsConstructor
@Slf4j
public class ChatMessageController {

    private final static String CHAT_EXCHANGE_NAME = "chat.exchange";

    private final ChatMessageService chatMessageService;
    private final RabbitTemplate template;

     @MessageMapping("chat.message")
    public void sendMessage(ChatDto.ChatMessageDto message) {
        try {
            ChatMessage newChat = chatMessageService.createChatMessage(message);
            if (newChat != null) {
                template.convertAndSend(CHAT_EXCHANGE_NAME, "room." + message.getRoomId(), newChat);
                log.info("Message sent to RabbitMQ: {}", newChat);
            } else {
                log.error("Failed to create chat message. User might not be in the chat room. User: {}, Room: {}",
                        message.getAuthorId(), message.getRoomId());
            }
        } catch (Exception e) {
            log.error("Error processing message: ", e);
        }
    }
}

ChatMessageServiceImpl

@Service
@RequiredArgsConstructor
public class ChatMessageServiceImpl implements ChatMessageService{

    private final ChatRoomRepository chatRoomRepository;

    @Override
    public ChatMessage createChatMessage(ChatDto.ChatMessageDto chatMessageDto) {

        ChatRoom chatRoom = chatRoomRepository.findById(chatMessageDto.getRoomId())
                .orElseThrow(() -> new RuntimeException("Chat room not found"));

        boolean exists = chatRoom.getChatRoomMembers().stream()
                .anyMatch(member -> member.getUsername().equals(chatMessageDto.getAuthorId()));

        if (!exists) {
            log.error("User not found in chat room: {}", chatMessageDto.getAuthorId());
            return null;
        }

        ChatMessage chatMessage = chatMessageDto.toEntity();
        chatRoom.setLastChatMesg(chatMessage);
        chatRoomRepository.save(chatRoom);

        return chatMessage;
    }
}

ChatMessageDto

/**
     * 웹소켓 접속시 요청 Dto
     */
@Data
@Builder
@NoArgsConstructor
@AllArgsConstructor
public static class ChatMessageDto {
    private String roomId;
    private String authorId;
    private String message;

    /* Dto -> Entity */
    public ChatMessage toEntity() {
        ChatMessage chatMessage = ChatMessage.builder()
                .roomId(roomId)
                .authorId(authorId)
                .message(message)
                .createdAt(LocalDateTime.now())
                .build();
        return chatMessage;
    }
}

채팅 메시지 처리하는 컨트롤러의 주요 기능

@MessageMapping("chat.message")로 설정하여 클라이언트로부터 /pub/chat.message 목적지로 전송된 STOMP 메시지를 처리한다.

template.convertAndSend() 메소드를 사용하여 메시지를 RabbitMQ로 전송한다.

메시지는 chat.exchange로 전송되며, 라우팅 키는 room. + 메시지의 방 ID로 구성된다.

기존 [재능교환소] Spring Boot로 Stomp 기반 1:1 채팅 구현 (with React) 포스팅에서는 Spring의 내장 STOMP 브로커를 사용하였다.

이때는 헤더의 AccessToken을 통해 사용자 ID를 추출하고, 이를 STOMP 세션에 저장하여 사용했다. 그러나 RabbitMQ로 전환하면서 이 방식이 더 이상 유효하지 않다는 것을 발견했다.

RabbitMQ는 외부 브로커로서 Spring의 STOMP 세션을 직접 관리하지 않기 때문에, 연결 시 헤더에서 검증한 토큰으로부터 추출한 사용자 ID를 세션에 저장하는 것이 불가능하며 메시지를 보낼 때마다 저장된 세션 정보에서 사용자 ID를 가져오는 것도 할 수 없었다.

이러한 제약을 해결하기 위해, 접근 방식을 변경하였다.

클라이언트가 메시지를 보낼 때 authorId를 JSON 페이로드에 직접 포함시켰다.

서버에서는 이 authorId를 사용해 해당 사용자가 채팅방에 존재하는지, 그리고 메시지를 보낼 권한이 있는지 확인하는 유효성 검사를 수행한다.

이 방식으로 매 메시지마다 사용자의 권한을 확인할 수 있어, 세션 저장의 한계를 우회하면서도 보안성을 유지할 수 있다.

이 새로운 접근 방식은 외부 브로커 사용에 따른 세션 관리의 복잡성을 피하고, 처리 로직을 단순화하면서도 필요한 보안 검증을 수행할 수 있게 해준다.

🧁 APIC로 STOMP 테스트 및 RabbitMQ Management 확인

APIC로 테스트 하러 가기

Request URL에는 websocket을 연결하기 위해 ws://localhost/chat/inbox을 적어준다.

그리고 Connection type에 WebSocket 대신 Stomp를 클릭해주고, Stomp Subscription URL에는 /exchange/chat.exchange/room.{roomId}을 적어준다.

/exchange/chat.exchange/room.{roomId}

/exchange: 메시지가 RabbitMQ exchange로 라우팅되어야 함 chat.exchange: RabbitConfig에서 정의한 exchange의 이름 room.{roomId}: 라우팅 키의 패턴으로 ChatMessageController에서 메시지를 보낼 때 사용한 라우팅 키와 일치 "."을 구분자로 사용: WebSocketConfig에서 AntPathMatcher를 .을 구분자로 설정

이로 인해 클라이언트는 특정 채팅방(roomId)에 대한 메시지만 구독이 가능하다.

동일하게 APIC 테스터를 두 개를 열어 놓고 한 곳에서 메세지를 보내보자.

Send의 Destination Queue에는 메세지 발행 요청을 위해 /pub/chat.message라고 적어준다.

옆에 json형태로 메세지를 보내줄 건데, 위에서 본 DTO 형식 그대로 적어주면 된다.

{
    "roomId" : "10ec8870-64b6-40cc-869f-17b1df2bc21e",
    "authorId": "kakao_sksk436@nate.com",
    "message" : "소셜로그인 계정입니다"
}

그럼 상대방에게도 메세지가 정상 수신되는 것을 확인할 수 있다.

메세지가 정상 수신되면 Overview에선 메세지가 방금 전송되었다고 Message rates에 표시가 되는 것을 확인할 수 있다.

참고

RabbitMQ를 실행한 후 터미널에서 rabbitmq-plugins enable rabbitmq_management를 친 후에 브라우저에 http://localhost:15672로 접속하면 RabbitMQ Managemnt 창에 들어갈 수 있다.

어플리케이션을 실행하면 RabbitMQ와 커넥션이 활성화되고, 소켓을 2개 연결했기 때문에 이름이 127.0.0.1:61826과 127.0.0.1:61829가 생겼다.

Queues and Streams에도 두 개의 Queue가 생겼다.

이처럼 RabbitMQ 웹 관리 콘솔창에서 실시간으로 다양한 정보를 확인할 수 있다!

출처

RabbitMQ Exchanges

문제사항

플래티넘 4단계 문제였다.

[백준] 1753번 최단경로(JAVA)와 [백준] 1916번 최소비용 구하기(JAVA) 문제와 마찬가지로 다익스트라 알고리즘 문제이다.

일반적인 다익스트라는 최소 거리를 구해 도출하면 됐었지만, 이 문제는 k개의 최단 거리를 구해야한다.

기존에 int[] D = new int[V + 1];로 선언했던 1차원 int형 배열로 사용하면 안된다. 따라서 우선순위큐 배열을 사용한다. PriorityQueue<Integer>[] distQue = new PriorityQueue[n + 1];

문제에서 k개의 최단거리를 구하라고 하였기 때문에 모든 최단거리를 저장할 필요 없다. 주어진 k개의 최단거리만 저장하자.

만약 우선순위큐 배열에 k개보다 작은 최단거리가 저장되어 있다면 새로운 경로를 다익스트라 알고리즘으로 저장한다.

우선순위큐 배열은 Comparator를 적용하여 사용하는 비교자를 커스터마이징하였기 때문에 자동으로 정렬된다.

k개 이상 최단거리가 저장되어 있는데 새로운 경로가 발생하면 우선순위큐 배열에 저장되어 있는 가장 큰 값보다 작으면 가장 큰 값을 꺼내서 삭제하고, 새로운 경로를 추가해주었다.

알고리즘 분류

그래프 (다익스트라)

코드

import java.io.*;
import java.util.*;
public class Main {

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

        int n = Integer.parseInt(st.nextToken()); //노드
        int m = Integer.parseInt(st.nextToken()); //에지
        int k = Integer.parseInt(st.nextToken());

        //인접 리스트
        ArrayList<Node>[] grape = new ArrayList[n + 1];

        for (int i = 0; i <= n; i++) {
            grape[i] = new ArrayList<>();
        }

        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            grape[a].add(new Node(b,c));
        }

        //최단거리 배열 -> 우선순위 큐 배열로 변경 (k번째를 구해야 함)
        PriorityQueue<Integer>[] distQue = new PriorityQueue[n + 1];
        //두 정수를 비교하여, 더 큰 정수가 우선순위가 높도록 설정
        Comparator<Integer> comparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 < o2 ? 1 : -1;
            }
        };
        for (int i = 0; i <= n; i++) {
            distQue[i] = new PriorityQueue<>(k, comparator);
        }

        PriorityQueue<Node> queue = new PriorityQueue<>();
        //작은 값이 맨 위로 올라가, 꺼낼 때 작은 값부터 꺼내게 됨 (Node에서 compareTo 메서드 오버라이딩)
        queue.add(new Node(1, 0));
        distQue[1].add(0);
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            for (Node node : grape[now.toNode]) {
                // 연결 관계 탐색
                if (distQue[node.toNode].size() < k) {
                    // 저장된 경로가 k개보다 작으면 경로 저장
                    distQue[node.toNode].add(now.e + node.e);
                    queue.add(new Node(node.toNode, now.e + node.e));
                } else if (distQue[node.toNode].peek() > now.e + node.e) {
                    // 저장된 경로가 k개이고, 새로운 경로가 가장 큰 값보다 작으면 추가 (k개보다 많이 저장할 필요 X)
                    distQue[node.toNode].poll(); // K번째 가장 큰 값 꺼내서 삭제
                    distQue[node.toNode].add(now.e + node.e); // 새로운 경로 값 추가
                    queue.add(new Node(node.toNode, now.e + node.e));
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (distQue[i].size() == k) {
                sb.append(distQue[i].peek()).append("\n");
            } else sb.append(-1).append("\n"); //k번째 경로 존재하지 않으면 -1
        }
        System.out.println(sb);
    }

    static class Node implements Comparable<Node> {
        int toNode;
        int e;

        @Override
        public int compareTo(Node node) {
            return this.e - node.e;
        }

        public Node(int toNode, int e) {
            this.toNode = toNode;
            this.e = e;
        }
    }
}

출처

[백준 1854] K번째 최단경로 찾기 (JAVA)

문제사항

골드 5단계 문제였다.

앞서 풀었던 [백준] 1753번 최단경로(JAVA)와 동일하게 다익스트라 알고리즘을 사용한 문제였다.

다익스트라 알고리즘에 대해 궁금하다면 위 포스팅을 참고하자.

사실 최단경로 문제는 최단거리 배열을 모두 출력하는 것이라면, 해당 문제는 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 구하는 것이므로 마지막 도착노드의 최소 비용(최단거리) 값을 출력하면 되기 때문에 유형은 똑같다고 볼 수 있다.

최단경로 문제를 풀 때는 방문 배열을 만들어서 노드의 방문 여부를 명시적으로 체크하였으나 이를 제외해도 충분히 코드 구현이 가능한 문제임을 깨달았다.

되려 방문 배열을 만들면 시간 초과가 뜬다는 것을 깨닫고, 방문 배열을 제거하고 D 배열만으로 방문 여부를 판단하였다.

이미 우선순위 큐에 최단거리 값을 가중치 값으로 넣어주기 때문에 충분히 판단이 가능한 것이다.

알고리즘 분류

그래프 (다익스트라)

코드

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

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

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        //인접 리스트
        ArrayList<Node>[] grape = new ArrayList[N + 1];
        //최단거리 배열
        int[] D = new int[N + 1];

        for (int i = 0; i <= N; i++) {
            grape[i] = new ArrayList<>();
            D[i] = Integer.MAX_VALUE;
        }

        StringTokenizer st;
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            grape[A].add(new Node(B, C));
        }

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        //다익스트라 -> 우선순위 큐
        PriorityQueue<Node> que = new PriorityQueue<>();
        //출발 도시 최단거리 0
        D[start] = 0;
        que.offer(new Node(start, 0));

        while (!que.isEmpty()) {
            Node now = que.poll();

            if (now.e > D[now.toNode]) continue;  // 이미 더 짧은 경로를 찾았다면 스킵

            for (Node next : grape[now.toNode]) {
                int newCost = D[now.toNode] + next.e;
                if (newCost < D[next.toNode]) {
                    D[next.toNode] = newCost;
                    que.offer(new Node(next.toNode, newCost)); //이미 우선순위 큐에 최단거리 값을 가중치 값으로 넣어주기 때문에 중복 검증 피할 수 있음
                }
            }
        }
        System.out.println(D[end]);
    }

    static class Node implements Comparable<Node> {
        int toNode;
        int e;
        @Override
        public int compareTo(Node node) { //가중치 비교 (작은 값)
            return this.e - node.e;
        }

        public Node(int toNode, int e) {
            this.toNode = toNode;
            this.e = e;
        }
    }
}

지난 포스팅에서 [재능교환소] Spring Boot+React 카카오 로그인 흐름 (JWT) 및 [재능교환소] Spring Security, OAuth2, JWT를 통한 소셜 로그인 구현 (Kakao, Google)을 구현한 내용을 정리하였다.

사용자 정보를 받아 DB에 저장된 사용자라면 JWT로 Access Token 발급 & UUID로 Refresh Token를 만들어 반환하고, DB에 없는 사용자라면 회원가입을 진행하는 과정까지 마무리하였었다.

여기서 발급하는 Access Token과 Refresh Token은 필자의 서버, 즉 진행하는 서비스에서 발급하는 (일반 로그인과 동일하게 진행하기 위해) 토큰이다.

카카오 서버에서도 발급해주는 AccessToken이 있었고, 이를 가지고 카카오 로그인한 사용자의 정보를 가져온다.

하지만 이전 로그인 구현 과정까지 카카오 서버에서 발급해주는 AceessToken을 따로 관리하지 않았기에 카카오 로그아웃 및 회원탈퇴 기능을 구현하는데 어려움이 존재하였다.

따라서 카카오 소셜 로그인 요청이 들어오면 카카오 서버의 AccessToken을 Redis에 저장하고, 이를 이용해 로그아웃 및 회원탈퇴 기능을 구현하였다.

필자가 구현한 소셜 로그인은 카카오, 구글 둘 다 있음에 유의하자.

그럼 다시 소셜 로그인을 구현한 Spring Security에 설정해 놓은 UserOAuth2Service 로 돌아가 코드를 추가해보자

소셜 로그인 구현 과정은 하단 링크로 들어가면 볼 수 있다.

[재능교환소] Spring Security, OAuth2, JWT를 통한 소셜 로그인 구현 (Kakao, Google)

🌱 소셜 로그인 시 카카오/구글 서버에서 AccessToken 받아와서 저장하기

RedisUtil

@Component
@RequiredArgsConstructor
public class RedisUtil {
    private final RedisTemplate<String, Object> redisTemplate;

    .. (일부 코드 생략)

    // 소셜 로그인 탈퇴를 위해 저장, 만료일, 삭제 등

    /**
     * 만료시간 설정 -> 자동삭제
     */
    @Transactional
    public void setValuesWithTimeout(String key, String value, long timeout){
        redisTemplate.opsForValue().set(key, value, timeout, TimeUnit.MILLISECONDS);
    }

    /**
     * 키 삭제
     */
    @Transactional
    public void deleteValues(String key) {
        redisTemplate.delete(key);
    }


    /**
     * 키를 이용한 값 확인
     */
    public Object getValues(String key) {
        return redisTemplate.opsForValue().get(key);
    }
}

앞서 말했듯이 카카오(혹은 구글) 서버에서 발급해주는 AccessToken을 Redis에 저장하기 위해 위 메서드들을 추가하였다.

UserOAuth2Service

@Slf4j
@RequiredArgsConstructor
@Service
public class UserOAuth2Service implements OAuth2UserService<OAuth2UserRequest, OAuth2User> {

    private final UserRepository userRepository;
    private final RedisUtil redisUtil;
    private final long ACCESS_TOKEN_EXPIRATION = 3600 * 1000;

    @Override
    public OAuth2User loadUser(OAuth2UserRequest userRequest) throws OAuth2AuthenticationException {
        OAuth2UserService<OAuth2UserRequest, OAuth2User> service = new DefaultOAuth2UserService();
        OAuth2User oAuth2User = service.loadUser(userRequest);  // OAuth2 정보를 가져옵니다.
        log.error("OAuth2User attributes: {}", oAuth2User.getAttributes());

        // 카카오(혹은 구글) 서버에서 발급해주는 AccessToken 추출
        String oauth2AccessToken = userRequest.getAccessToken().getTokenValue();

        Map<String, Object> originAttributes = oAuth2User.getAttributes(); // OAuth2User의 attribute

        // OAuth2 서비스 id (google, kakao)
        String registrationId = userRequest.getClientRegistration().getRegistrationId();    // 소셜 정보를 가져옵니다.

        // OAuthAttributes: OAuth2User의 attribute를 서비스 유형에 맞게 담아줄 클래스
        OAuthAttributes attributes = OAuthAttributes.of(registrationId, originAttributes);

        if (!userRepository.findById(attributes.getEmail()).isPresent()) { //db에 해당 회원정보 없다면 저장
            userRepository.save(attributes.toEntity());
        }

        /* 레디스 토큰 정보 */
        redisUtil.setValuesWithTimeout("AT(oauth2):" + attributes.getEmail() ,oauth2AccessToken, ACCESS_TOKEN_EXPIRATION);

        List<GrantedAuthority> authorities = Collections.singletonList(new SimpleGrantedAuthority("ROLE_USER"));

        return new OAuth2CustomUser(registrationId, originAttributes, authorities, attributes.getEmail());
    }

}

/* 레디스 토큰 정보 */
redisUtil.setValuesWithTimeout("AT(oauth2):" + attributes.getEmail() ,oauth2AccessToken, ACCESS_TOKEN_EXPIRATION);

소셜 로그인 시에 카카오 혹은 구글에서 받아온 AccessToken을 Redis에 저장하는 작업을 추가해주었다.

소셜 로그인은 보통 AccessToken을 유효시간을 약 1시간으로 한다.

🌵 소셜 로그인 후 로그아웃하기

설명

먼저 어떤 과정으로 소셜 로그인 후에 로그아웃이 이루어져야 하는지 살펴보자.

< 카카오/구글 로그아웃 과정 >

1. 클라이언트에서 로그아웃 요청한다.

2. 서버에서는 자체 발급한 액세스/리프레시 토큰을 무효화한다.

3. 서버에서 카카오 로그아웃 API를 호출하여 카카오 액세스 토큰을 무효화한다.

4. 카카오 서버에서는 사용자의 동의 정보를 계속 유지하고 있게 된다.

5. 따라서 동일한 사용자가 다시 로그인하면 동의 절차 없이 자동으로 로그인된다.

여기서 키 포인트는 카카오/구글 서버 측에서는 로그아웃 후에도 사용자의 동의 정보를 보관하고 있기 때문에, 다음 로그인 시 자동으로 인증 코드를 발급하고 로그인이 완료되는 것이다.

그럼 실제 구현한 소스코드를 살펴보자.

구현

UserController

@RestController
@RequiredArgsConstructor
@RequestMapping("/v1/user/")
@Slf4j
public class UserController {

    private final AuthService authService;

    ...(생략)

    /**
     * 로그아웃
     */
    @PatchMapping("/logout")
    public UserDto.ResponseBasic logout(HttpServletRequest request) {
        return authService.logout(request);
    }
}

AuthServiceImpl

@Service
@RequiredArgsConstructor
@Slf4j
public class AuthServiceImpl implements AuthService{

    private final JwtService jwtService;
    private final RefreshRepository refreshRepository;
    private final SecurityUtil securityUtil;
    private final RedisUtil redisUtil;

    @Override
    public UserDto.ResponseBasic logout(HttpServletRequest request) {
        // 액세스/리프레시 토큰 무효화
        String id = invalidateToken(request);

        /* oauth2 access 토큰 삭제 */
        if (redisUtil.getValues("AT(oauth2):" + id) != null) {
            String socialAccessToken = (String) redisUtil.getValues("AT(oauth2):" + id);
            int underscoreIndex = id.indexOf("_");
            if (underscoreIndex != -1) {
                String socialType = id.substring(0, underscoreIndex);
                if (socialType.equals("google")) {
                    googleLogout(socialAccessToken);
                } else if (socialType.equals("kakao")) {
                    kakaoLogout(socialAccessToken);
                }
            }
            redisUtil.deleteValues("AT(oauth2):" + id);
        }


        return new UserDto.ResponseBasic(200, "로그아웃 되었습니다.");
    }

    // 액세스/리프레시 토큰 무효화
    private String invalidateToken(HttpServletRequest request) {
        String token = request.getHeader("Authorization").substring(7);
        Date date = jwtService.extractExpiration(token);
        Long now = new Date().getTime();
        Long expiration = date.getTime() - now;
        String id = securityUtil.getCurrentMemberUsername();

        // 엑세스 토큰 블랙리스트 관리
        redisUtil.setBlackList(token, "logout", Duration.ofMillis(expiration));

        // 리프레시 토큰 삭제
        if (refreshRepository.findById(id).isPresent()) {
            refreshRepository.deleteById(id);
        }
        return id;
    }

    public void kakaoLogout(String access_Token) {
        String reqURL = "https://kapi.kakao.com/v1/user/logout";
        try {
            URL url = new URL(reqURL);
            HttpURLConnection conn = (HttpURLConnection) url.openConnection();
            conn.setRequestMethod("POST");
            conn.setRequestProperty("Authorization", "Bearer " + access_Token);

            int responseCode = conn.getResponseCode();
            System.out.println("responseCode : " + responseCode);

            BufferedReader br = new BufferedReader(new InputStreamReader(conn.getInputStream()));

            String result = "";
            String line = "";

            while ((line = br.readLine()) != null) {
                result += line;
            }
            System.out.println(result);
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

    public void googleLogout(String accessToken) {
        String tokenInfoUrl = "https://oauth2.googleapis.com/tokeninfo?access_token=" + accessToken;
        try {
            URL url = new URL(tokenInfoUrl);
            HttpURLConnection conn = (HttpURLConnection) url.openConnection();
            conn.setRequestMethod("GET");
            int responseCode = conn.getResponseCode();
            System.out.println("Google Logout Response Code: " + responseCode);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

컨트롤러에서 로그아웃 요청 엔드포인트를 만들었다.

 String id = invalidateToken(request);

// 액세스/리프레시 토큰 무효화
private String invalidateToken(HttpServletRequest request) {
    String token = request.getHeader("Authorization").substring(7);
    Date date = jwtService.extractExpiration(token);
    Long now = new Date().getTime();
    Long expiration = date.getTime() - now;
    String id = securityUtil.getCurrentMemberUsername();

    // 엑세스 토큰 블랙리스트 관리
    redisUtil.setBlackList(token, "logout", Duration.ofMillis(expiration));

    // 리프레시 토큰 삭제
    if (refreshRepository.findById(id).isPresent()) {
        refreshRepository.deleteById(id);
    }
    return id;
}

위와 같이 SpringBoot에서는 서비스 내에서 발급한 Access/Refresh Token을 무효화한다.

/* oauth2 access 토큰 삭제 */
if (redisUtil.getValues("AT(oauth2):" + id) != null) {
    String socialAccessToken = (String) redisUtil.getValues("AT(oauth2):" + id);
    int underscoreIndex = id.indexOf("_");
    if (underscoreIndex != -1) {
        String socialType = id.substring(0, underscoreIndex);
        if (socialType.equals("google")) {
            googleLogout(socialAccessToken);
        } else if (socialType.equals("kakao")) {
            kakaoLogout(socialAccessToken);
        }
    }
    redisUtil.deleteValues("AT(oauth2):" + id);
}

다음은 카카오/구글 서버에서 발급받았던 AccessToken과 함께 카카오/구글 서버의 로그아웃 API를 호출하여 AccessToken을 무효화 시켜야 한다.

필자는 DB에 저장된 userId가 소셜로그인 한 유저라면 Provider_이메일주소로 저장이 되기 때문에 Provider 부분을 추출하여 카카오와 구글을 구분 지었다.

그리고 Provider가 kakao라면 kakaoLogout 메서드를 호출하여 카카오 로그아웃 API를 호출하여 액세스 토큰을 무효화 시키고, Provider가 google이라면 googleLogout 메서드를 호출하여 구글 로그아웃 API를 호출하여 액세스 토큰을 무효화 시킨다.

카카오 로그아웃 Rest API

필자는 카카오 로그아웃은 액세스 토큰 방식을 사용하였다.

구글 로그아웃 Rest API

🍀 소셜 로그인 후 회원탈퇴하기

설명

먼저 어떤 과정으로 소셜 로그인 후에 회원탈퇴가 이루어져야 하는지 살펴보자.

< 카카오/구글 회원탈퇴 과정 >

1. 카카오/구글 연결 끊기 API 호출 카카오/구글에서 제공하는 '연결 끊기(unlink)' API를 호출한다. 이 API는 사용자의 카카오 계정과 해당 서비스 간의 연동을 해제한다.

   만약 레디스에 저장된 카카오/구글 AceessToken이 만료되었다면 다시 로그인해야 한다. 따라서 에러 메세지와 404 에러코드를 응답으로 내보낸다. 또한 만료 시에는 서비스용 액세스 토큰과 리프레시 토큰을 무효화하기 때문에 인증이 필요한 다른 api를 호출해도 다시 로그인해달라는 메세지와 404 에러코드를 내보낸다.

2. 카카오 동의 내역 삭제 연결 끊기 API 호출로 인해 카카오 서버에서 해당 서비스에 대한 사용자의 동의 내역이 삭제된다.

3. 토큰 무효화 서비스에서 발급한 리프레시 토큰을 무효화한다.

4. 서비스 내 회원 정보 삭제 사용자의 개인 정보, 활동 내역 등 서비스 내부 데이터베이스에 저장된 모든 관련 정보를 삭제하거나 비활성화한다.

5. 클라이언트 측 정리 클라이언트 앱이나 웹에서 저장된 모든 관련 데이터(로컬 스토리지, 쿠키 등)를 삭제한다.

6. 사용자에게 확인 회원 탈퇴 절차가 완료되었음을 사용자에게 알린다.

구현

UserController

@RestController
@RequiredArgsConstructor
@RequestMapping("/v1/user/")
@Slf4j
public class UserController {

    private final AuthService authService;

    ...(생략)

    /**
     * 회원탈퇴
     */
    @PostMapping("/withdraw")
    public UserDto.ResponseBasic withdraw(HttpServletRequest request) {
        return authService.withdraw(request);
    }
}

AuthServiceImpl

@Service
@RequiredArgsConstructor
@Slf4j
public class AuthServiceImpl implements AuthService{

    private final UserRepository userRepository;
    private final JwtService jwtService;
    private final RefreshRepository refreshRepository;
    private final SecurityUtil securityUtil;
    private final RedisUtil redisUtil;
    private final TalentRepository talentRepository;
    private final CommentRepository commentRepository;

 @Override
    public UserDto.ResponseBasic withdraw(HttpServletRequest request) {
        String id = SecurityUtil.getCurrentMemberUsername();

        /* 카카오 및 구글 연결 해제 */
        int underscoreIndex = id.indexOf("_");
        if (underscoreIndex != -1) {
            String socialType = id.substring(0, underscoreIndex);
            if (socialType.equals("google")) {
                googleUnlink(id, request);
            } else if (socialType.equals("kakao")) {
                kakaoUnlink(id, request);
            }
        }

        if (refreshRepository.findById(id).isPresent()) { //리프레시 토큰 삭제
            refreshRepository.deleteById(id);
        }
        List<Talent> talents = talentRepository.findByWriterId(id);
        if (!talents.isEmpty()) {
            for (Talent talent : talents) {
                talent.changeUserNull();
            }
        }
        List<Comment> comments = commentRepository.findByWriterId(id);
        if (!comments.isEmpty()) {
            for (Comment comment : comments) {
                comment.changeUserNull();
            }
        }

        userRepository.deleteById(id);

        return new UserDto.ResponseBasic(200, "회원 탈퇴가 정상적으로 처리되었습니다.");
    }

    // 액세스/리프레시 토큰 무효화
    private String invalidateToken(HttpServletRequest request) {
        String token = request.getHeader("Authorization").substring(7);
        Date date = jwtService.extractExpiration(token);
        Long now = new Date().getTime();
        Long expiration = date.getTime() - now;
        String id = securityUtil.getCurrentMemberUsername();

        // 엑세스 토큰 블랙리스트 관리
        redisUtil.setBlackList(token, "logout", Duration.ofMillis(expiration));

        // 리프레시 토큰 삭제
        if (refreshRepository.findById(id).isPresent()) {
            refreshRepository.deleteById(id);
        }
        return id;
    }

    public void kakaoUnlink(String id, HttpServletRequest request) {
        String accessToken = (String) redisUtil.getValues("AT(oauth2):" + id);
        // oauth2 토큰이 만료 시 재 로그인
        if (accessToken == null) {
            invalidateToken(request);
            throw SocialLoginRequriedException.EXCEPTION;
        } else {
            redisUtil.deleteValues("AT(oauth2):" + id);
        }

        String reqURL = "https://kapi.kakao.com/v1/user/unlink";
        try {
            URL url = new URL(reqURL);
            HttpURLConnection conn = (HttpURLConnection) url.openConnection();
            conn.setRequestMethod("POST");
            conn.setRequestProperty("Authorization", "Bearer " + accessToken);

            int responseCode = conn.getResponseCode();
            System.out.println("responseCode : " + responseCode);

            BufferedReader br = new BufferedReader(new InputStreamReader(conn.getInputStream()));

            String result = "";
            String line = "";

            while ((line = br.readLine()) != null) {
                result += line;
            }
            System.out.println(result);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void googleUnlink(String id, HttpServletRequest request) {
        String accessToken = (String) redisUtil.getValues("AT(oauth2):" + id);
        // oauth2 토큰이 만료 시 재 로그인
        if (accessToken == null) {
            invalidateToken(request);
            throw SocialLoginRequriedException.EXCEPTION;
        } else {
            redisUtil.deleteValues("AT(oauth2):" + id);
        }
        String tokenInfoUrl = "https://oauth2.googleapis.com/revoke";
        try {
            URL url = new URL(tokenInfoUrl);
            HttpURLConnection conn = (HttpURLConnection) url.openConnection();
            conn.setRequestMethod("POST");
            conn.setRequestProperty("Content-Type", "application/x-www-form-urlencoded");
            conn.setDoOutput(true);

            String postData = "token=" + accessToken;
            byte[] postDataBytes = postData.getBytes("UTF-8");

            conn.setRequestProperty("Content-Length", String.valueOf(postDataBytes.length));

            try (DataOutputStream wr = new DataOutputStream(conn.getOutputStream())) {
                wr.write(postDataBytes);
            }

            int responseCode = conn.getResponseCode();
            System.out.println("Google Unlink Response Code: " + responseCode);

            BufferedReader in = new BufferedReader(new InputStreamReader(conn.getInputStream()));
            String inputLine;
            StringBuilder response = new StringBuilder();
            while ((inputLine = in.readLine()) != null) {
                response.append(inputLine);
            }
            in.close();

        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

먼저 카카오/구글 연결 끊기 API 호출해야 한다.

/* 카카오 및 구글 연결 해제 */
int underscoreIndex = id.indexOf("_");
if (underscoreIndex != -1) {
    String socialType = id.substring(0, underscoreIndex);
    if (socialType.equals("google")) {
        googleUnlink(id, request);
    } else if (socialType.equals("kakao")) {
        kakaoUnlink(id, request);
    }
}

만약 카카오 로그인을 한 유저라면 kakaoUnlink 메서드를 호출하는데, 여기서 레디스에 저장된 카카오 AccessToken을 가져오는게 선행되어야 한다.

하지만 카카오 액세스 토큰은 유효시간 1시간 미만이기에 만약 유효시간이 지나면 자동으로 레디스에서 삭제될 것이다.

그렇기에 액세스 토큰이 null인 경우, 토큰을 무효화하고 SocialLoginRequiredException 예외를 발생시켰다.

레디스에 카카오 액세스 토큰이 저장되어 유효시간이 지나 자동으로 삭제되었다면 회원 탈퇴 시 위와 같은 에러 메세지와 404 에러코드가 뜬다.

고로 액세스 토큰이 헤더에 있다 한들, 블랙리스트에 등록하였기 때문에 인증이 필요한 엔드포인트엔 접근이 불가능하다.

레디스에 카카오 액세스 토큰이 남아있다면 카카오/구글 연결 끊기 API가 정상적으로 호출이 된다.

이후엔 레디스에 저장된 서비스에서 사용 중인 리프레시 토큰이 삭제되고, 사용자와 연관관계인 엔티티와의 관계로 끊은 뒤 정상적으로 DB에서 사용자 정보가 삭제된다.

사용자가 작성한 재능교환소 게시물은 삭제하고, 사용자가 작성한 댓글은 null로 변경해주어 연관관계를 제거하였다.

1. 재능교환 게시물 삭제 이유 사용자가 작성한 재능교환소 게시물은 완전히 삭제된다. 이는 탈퇴한 사용자의 게시물에 대해 다른 사용자가 더 이상 재능교환 요청을 보낼 수 없어 실질적인 가치를 잃기 때문이다. 불필요한 정보를 제거함으로써 시스템의 효율성을 유지하였다.

2. 댓글의 fk인 사용자를 null로 변경하여 연관관계 제거 기존 댓글(부모 및 자식 댓글)의 맥락과 정보의 연속성을 유지한다. 다른 사용자들끼리와의 정보 교환에 대한 기록을 보존한다.

🌾 느낀점

이전에 Session 방식과 서버사이드 렌더링으로 구현했던 소셜 로그인을 이번에는 토큰 기반의 인증 방식으로 새롭게 구현하면서, 인증 시스템의 다양한 접근 방식과 각각의 장단점을 깊이 이해할 수 있었다.

블로그에 구현 과정을 정리하면서, 개념을 더욱 명확히 이해하고 체계화할 수 있었다. 특히 로그아웃과 회원 탈퇴 같은 덜 다뤄진 주제에 대해 정리한 것은 다른 개발자들에게도 도움이 될 수 있기를.. 😯

소셜 로그인 구현 과정에서 OAuth 2.0 프로토콜의 세부사항과 보안 고려사항을 깊이 있게 다루면서, 웹 애플리케이션 보안의 중요성을 새삼 실감했다.

이번 소셜 로그인 구현 경험은 기술적 역량 향상뿐만 아니라, 개발자로서의 전반적인 시야를 넓히는 기회였다고 생각한다.

앞으로도 이러한 과제들을 통해 지속적으로 성장해 나가고, 배운 내용을 공유하며 함께 발전해 나가고 싶다.

🌿 출처

[Spring boot] spring security 자체 로그인 + 소셜 로그인 백엔드에서 모두 처리 시 회원 탈퇴 (카카오, 구글, 네이버 연결 끊기)

[재능교환소] 프로젝트를 만들면서 필요한 필수 기능이 채팅 이다.

재능교환 게시물을 올리면 사용자끼리 소통이 이루어져야 매칭서비스가 가능하기 때문에 쪽지 혹은 채팅 기능은 필수였다.

쪽지와 채팅 둘 중 어느 기능을 구현할까 고민하다가 1:1 채팅을 구현하기로 하였다.

필자는 백엔드를 맡았기 때문에 소스코드는 백엔드 위주로 설명하려고 한다.

🌼 개념

WebSocket

ws 프로토콜을 기반으로 한 클라이언트와 서버 사이에 지속적인 완전 양방향 연결 스트림을 만들어 주는 기술이다.

웹소켓(Websocket) 은 HTTP 와 구분되는 통신 프로토콜이다.

HTTP 통신은 요청 (Request) 와 응답 (Response) 이 존재한다.

여기서 요청은 클라이언트가, 응답은 서버가 전송한다.

이런 구조로 서버는 능동적으로 클라이언트에 ‘먼저’ 데이터를 전송할 수 없다.

따라서 클라이언트는 서버의 데이터를 얻기 위해 항상 요청을 해야하고, 서버는 이에 수동적으로 응답해주는 구조로 구성되어있다.

이와 같은 통신 구조를 반이중통신(Half-Duplex Communication) 이라고 한다.

HTTP 통신과 다르게 웹소켓은 TCP/IP 의 소켓과 마찬가지로 전이중통신(Full-Duplex Communication)을 지원한다.

웹소켓으로 연결된 서버와 클라이언트는 각 주체가 요청과 응답없이 능동적으로 메세지를 보낼 수 있다.

따라서 웹소켓은 전이중통신과 실시간 네트워킹이 보장되어야 하는 환경에서 유용하게 사용될 수 있다.

Stomp

STOMP는 Simple Text Oriented Messaging Protocol의 약자이다.

Stomp는 메시지 전송을 효율적으로 하기 위한 프로토콜로, 기본적으로 pub와 sub 구조로 되어있다.

pub : 메시지를 전송하고

sub : 전송한 메세지를 받아서 처리하는 구조

STOMP 프로토콜은 클라이언트/서버 간 전송할 메시지의 유형, 형식, 내용들을 정의한 규칙이다.

TCP 또는 WebSocket과 같은 [양방향 네트워크 프로토콜 기반]으로 동작한다.

헤더에 값을 세팅할 수 있어서 헤더 값을 기반으로 통신 시 인증처리를 구현할 수 있다.

pub / sub 구조

pub/sub란 메시지를 공급하는 주체와 소비하는 주체를 분리해 제공하는 메시징 방법이다.

우체통(Topic)이 있다면 집배원(Publisher)이 신문을 우체통에 배달하는 행위가 있고, 우체통에 신문이 배달되는 것을 기다렸다가 빼서 보는 구독자(Subscriber)의 행위가 있다. 이때 구독자는 다수가 될 수 있다.

즉, 채팅방을 생성하는 것은 우체통 Topic을 만드는 것이고 채팅방에 들어가는 것은 구독자로서 Subsciber가 되는 것이다. 채팅방에 글을 써서 보내는 행위는 우체통에 신문을 넣는 Publisher가 된다.

Message Brocker

이때 Message Brocker란 개념이 있다.

이것은 [Publisher]로 부터 전달받은 메시지를 [Subscriber]에게 메시지를 주고 받게 해주는 중간 역할 하는 것을 말한다.

클라이언트는 SEND, SUBSCRIBE 명령을 통해서 메시지의 내용과 수신 대상을 설명하는 "destination" 헤더와 함께 메시지에 대한 전송이나 구독을 할 수 있다.

이것이 브로커를 통해 연결된 다른 클라이언트로 메시지를 보내거나, 서버로 메시지로 보내 일부 작업을 요청할 수 있는 PUB/SUB 메커니즘을 가능하게 한다.

스프링이 지원하는 Stomp에서는 스프링 웹 소켓 애플리케이션이 클라이언트에게 Stomp 브로커의 역할을 한다. 이때 메시지는 @Controller 메시지 처리 방법이나, Subscriber를 추적해서 구독중인 사용자에게 메시지를 전파(Broadcast)하는 Simple In Momory 브로커에게 라우팅 된다.

이렇게 Spring 환경에서 추가적인 설정없이 Stomp 프로토콜을 사용하면 메시지 브로커는 자동으로 In Memory Brocker를 사용하게 된다.

🌷 Stomp를 사용한 1:1 채팅 구현

순서대로 소스코드를 살펴보자.

필자는 Maven을 사용하였기 때문에 pom.xml에 의존성을 추가해주었다.

pom.xml

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-websocket</artifactId>
</dependency>
<dependency>
    <groupId>org.springframework</groupId>
    <artifactId>spring-messaging</artifactId>
</dependency>
<dependency>
    <groupId>com.fasterxml.jackson.core</groupId>
    <artifactId>jackson-core</artifactId>
</dependency>
<dependency>
    <groupId>com.fasterxml.jackson.core</groupId>
    <artifactId>jackson-databind</artifactId>
</dependency>

Websocket을 사용하기 위해 Websocket dependency를 추가해주었다.

여기에 Stomp의 Message 기능을 위해 spring-messaging도 추가해주었다.

Stomp는 메세지를 json 형태로 사용하기 때문에 jackson-core(json)과 json을 dto로 자동 데이터 변환 해주는 jackson-databind가 필요하다.

WebSocketConfig

@Configuration
@EnableWebSocketMessageBroker
public class WebSocketConfig implements WebSocketMessageBrokerConfigurer {

    @Override
    public void registerStompEndpoints(StompEndpointRegistry registry) {

        // socketJs 클라이언트가 WebSocket 핸드셰이크를 하기 위해 연결할 endpoint를 지정할 수 있다.
        registry.addEndpoint("/chat/inbox")
                .setAllowedOriginPatterns("*") // cors 허용을 위해 꼭 설정해주어야 한다.
                .withSockJS(); //웹소켓을 지원하지 않는 브라우저는 sockJS를 사용하도록 한다.
    }

    @Override
    public void configureMessageBroker(MessageBrokerRegistry registry) {
        // 메모리 기반 메시지 브로커가 해당 api를 구독하고 있는 클라이언트에게 메시지를 전달한다.
        // to subscriber
        registry.enableSimpleBroker("/sub");

        // 클라이언트로부터 메시지를 받을 api의 prefix를 설정한다.
        // publish
        registry.setApplicationDestinationPrefixes("/pub");


    }
}

WebSocketMessageBrokerConfigurer 인터페이스를 구현한다.

두 번째 메서드에서 enableSimpleBroker가 위에서 언급한 메시지 브로커이다.

ws://localhost/chat/inbox를 호출하면 websocket 연결이 된다.

이후 /sub를 통해 채팅방에 구독 신청을 하고, 채팅 데이터를 전송할 때 마다 /pub 관련 메서드를 호출해 채팅방 구독하는 유저에게 메시지 브로커가 메시지를 전달할 것이다.

다음은 채팅을 위해 추가한 Entity를 살펴보자.

ChatRoom

@Data
@Entity
@Table(name = "ChatRoom")
@DynamicUpdate
@Builder
@EqualsAndHashCode(onlyExplicitlyIncluded = true)
@EntityListeners(value = {AuditingEntityListener.class})
@NoArgsConstructor
@AllArgsConstructor
public class ChatRoom {
    @EqualsAndHashCode.Include
    @Id
    @Column(name = "id")
    private String id;

    //단방향
    @OneToOne(fetch = FetchType.EAGER, cascade = CascadeType.ALL)
    @JoinColumn(name = "lastChatMesgId")
    private ChatMessage lastChatMesg;

    @ManyToMany(fetch = FetchType.EAGER, cascade = CascadeType.ALL)
    @JoinTable(name = "ChatRoom_Members",
            joinColumns = @JoinColumn(name = "chatRoomId"),
            inverseJoinColumns = @JoinColumn(name = "userId"))
    private Set<User> chatRoomMembers = new HashSet<>();

    @Column(name = "createdAt", updatable = false)
    @CreatedDate
    private LocalDateTime createdAt;

    public static ChatRoom create() {

        ChatRoom room = new ChatRoom();
        room.setId(UUID.randomUUID().toString());

        return room;
    }

    public void addMembers(User roomMaker, User guest) {
        this.chatRoomMembers.add(roomMaker);
        this.chatRoomMembers.add(guest);
    }
}

ChatMessage

@Data
@Entity
@Table(name = "ChatMessage")
@Builder
@EqualsAndHashCode(onlyExplicitlyIncluded = true)
@EntityListeners(value = {AuditingEntityListener.class})
@NoArgsConstructor
@AllArgsConstructor
public class ChatMessage {

    @EqualsAndHashCode.Include
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    @Column(name = "id")
    private Long id;

    @JoinColumn(name = "roomId", insertable = false, updatable = false)
    private String roomId; //단순히 ID 값만 필요  (ChatRoom)

    @JoinColumn(name = "authorId", insertable = false, updatable = false)
    private String authorId; //단순히 ID 값만 필요 (User)

    @Column(name = "message")
    private String message;

    @Column(name = "createdAt", updatable = false)
    @CreatedDate
    private LocalDateTime createdAt;
}

채팅 기능을 구현하려면 먼저 채팅이 이루어질 채팅방이 존재해야 한다.

따라서 채팅 메시지 통신 과정에 앞서, 채팅방을 생성하고 데이터베이스에 저장하는 단계가 선행되어야 한다.

필자는 먼저 채팅방 생성 API를 구현하여 데이터베이스에 저장하는 과정을 거쳤다.

그 다음에 실제 채팅 통신이 이루어질 때, 이전에 생성된 채팅방에 메시지를 저장하는 방식으로 구현하였다.

따라서 채팅 메시지 통신 과정을 설명하기에 앞서, 채팅방 개설 과정부터 먼저 살펴보자.

ChatRoomController

@RestController
@RequiredArgsConstructor
@RequestMapping("/v1/chatRoom/")
@Slf4j
public class ChatRoomController {

    private final ChatRoomService chatRoomService;

    @PostMapping("/personal") //개인 DM 채팅방 생성
    public ChatDto.CreateChatRoomResponse createPersonalChatRoom(@RequestBody ChatDto.CreateChatRoomRequest request) {
        return chatRoomService.createChatRoomForPersonal(request);
    }
}

CreateChatRoomRequest

/**
 * 채팅방 개설 요청 dto
 */
@Getter
public static class CreateChatRoomRequest {
    private String roomMakerId;
    private String guestId;
}

CreateChatRoomResponse

/**
 * 채팅방 개설 성공시 응답 dto
 */
@Getter
public static class CreateChatRoomResponse {
    private String roomMakerId;
    private String guestId;
    private String chatRoomId;

    /* Entity -> Dto */
    public CreateChatRoomResponse(String roomMakerId, String guestId, String chatRoomId) {
        this.roomMakerId = roomMakerId;
        this.guestId = guestId;
        this.chatRoomId = chatRoomId;
    }
}

ChatRoomServiceImpl

@Service
@RequiredArgsConstructor
public class ChatRoomServiceImpl implements ChatRoomService {

    private final UserRepository userRepository;
    private final ChatRoomRepository chatRoomRepository;
    private final SecurityUtil securityUtil;

    @Override // 개인 DM방 생성
    public ChatDto.CreateChatRoomResponse createChatRoomForPersonal(ChatDto.CreateChatRoomRequest chatRoomRequest) {
        String id = securityUtil.getCurrentMemberUsername(); //id=roomMakerId 같아야 함
        if (!id.equals(chatRoomRequest.getRoomMakerId())) {
            throw UserNotFoundException.EXCEPTION;
        }
        User roomMaker = userRepository.findById(id).orElseThrow(() -> UserNotFoundException.EXCEPTION);
        User guest = userRepository.findById(chatRoomRequest.getGuestId()).orElseThrow(() -> UserNotFoundException.EXCEPTION);

        ChatRoom newRoom  = ChatRoom.create();
        newRoom.addMembers(roomMaker, guest);

        chatRoomRepository.save(newRoom);

        return new ChatDto.CreateChatRoomResponse(roomMaker.getId(),guest.getId(), newRoom.getId());
    }
}

String id = securityUtil.getCurrentMemberUsername();는 SecurityContext에 저장된 User의 id를 가져오는 메서드이다.

ChatRoom의 id는 UUID로 랜점한 값으로 설정하여 채팅방을 만들었고, 로그인한 사용자와 대화할 사용자 id를 ChatRoom_Members 엔티티에 저장하였다.

DB에는 위와 같이 저장된다.

다음으로 실제로 채팅을 발행할 수 있게 만들어줄 수 있도록 엔드포인트가 호출되는 Controller를 살펴보자.

ChatMessageController

@Controller
@RequiredArgsConstructor
@Slf4j
public class ChatMessageController {
    private final ChatMessageService chatMessageService;
    private final ChatRoomService chatRoomService;
    private final SimpMessagingTemplate messagingTemplate;

    @MessageMapping("/message")
    public void sendMessage(ChatDto.ChatMessageDto message) {
        // 실시간으로 방에서 채팅하기
        ChatMessage newChat = chatMessageService.createChatMessage(message);
        log.info("received message: {}", message);

        // 방에 있는 모든 사용자에게 메시지 전송
        messagingTemplate.convertAndSend("/sub/channel/"+message.getRoomId(), newChat);
    }
}

ChatMessageDto

/**
 * 웹소켓 접속시 요청 Dto
 */
@Data
@Builder
@NoArgsConstructor
@AllArgsConstructor
public static class ChatMessageDto {
    private String roomId;
    private String authorId;
    private String message;

    /* Dto -> Entity */
    public ChatMessage toEntity() {
        ChatMessage chatMessage = ChatMessage.builder()
                .roomId(roomId)
                .authorId(authorId)
                .message(message)
                .createdAt(LocalDateTime.now())
                .build();
        return chatMessage;
    }
}

ChatMessageServiceImpl

@Service
@RequiredArgsConstructor
public class ChatMessageServiceImpl implements ChatMessageService{

    private final ChatRoomRepository chatRoomRepository;

    @Override
    public ChatMessage createChatMessage(ChatDto.ChatMessageDto chatMessageDto) {
        ChatMessage chatMessage = chatMessageDto.toEntity();
        ChatRoom chatRoom = chatRoomRepository.findById(chatMessage.getRoomId()).orElseThrow();
        chatRoom.setLastChatMesg(chatMessage);
        chatRoomRepository.save(chatRoom);

        return chatMessage;
    }
}

Stomp는 @MessageMapping을 이용하여 handler를 직접 구현하지 않고 controller를 따로 분리해서 관리 가능하다.

@MessageMapping

작성된 경로와 이전에 configuration에서 지정한 prefix인 /pub가 합쳐져 /pub/message로 메시지 발행 요청을 하는 것이다.

SimpleMessagingTemplate

simpleMessagingTemplate는 이전에 @EnableWebSocketMessageBroker를 통해 bean으로 등록된 것이다. 이를 통해 메시지 브로커로 데이터를 전달한다.

ChatMessageController 를 보면 messagingTemplate.convertAndSend("/sub/channel/"+message.getRoomId(), newChat); 라고 작성되어 있다.

이는 /sub/channel/{roomId}를 구독하고 있는 모든 사용자에게 메시지 전송된다는 뜻이다.

여기서 필자는 구독하고 있는 사용자들에게 메시지를 전송하기 전에 도착한 메세지를 DB에 저장하였다.

🌷 APIC로 Stomp 테스트-1

참고로 WebSocketConfig의 .withSockJS();는 주석 처리해주어야 테스트가 진행된다.

APIC로 테스트 하러 가기

현재 Postman으로는 Stomp 테스트가 불가하기 때문에 필자는 APIC로 Stomp를 테스트하였다.

들어가면 바로 테스트할 수 있는 창이 나오는데, 여기서 그대로 테스트를 진행하는게 아니라 상단에 ws 바를 클릭해준다.

Request URL에는 websocket을 연결하기 위해 ws://localhost/chat/inbox을 적어준다.

그리고 Connection type에 WebSocket 대신 Stomp를 클릭해주고, Stomp Subscription URL에는 앞서 말한 /sub/channel/{roomId}을 적어준다.

roomId는 채팅방을 생성해준 뒤 반환해주는 roomId 필드 값을 그대로 써주면 된다.

/sub/channel/6f3cfc9d-1504-4f9b-96cb-843cd96031e0 라고 필자는 적어주었다.

그리고 서버를 실행시켜준 뒤 Connect를 눌러준다.

Connect 대신 Disconnect로 변경되었고, Messages 부분에도 Somp connected 라고 뜬다.

새로운 창을 다시 띄어준뒤, 앞서 설정한 Request URL와 Subscription URL을 동일하게 작성해주고 Connect를 눌러준다.

그리고 Send의 Destination Queue에는 메세지 발행 요청을 위해 /pub/message라고 적어주었다.

옆에 json형태로 메세지를 보내줄 건데, 위에서 본 DTO 형식 그대로 적어주면 된다.

{
    "roomId" : "6f3cfc9d-1504-4f9b-96cb-843cd96031e0",
    "authorId" : "alswl3359",
    "message" : "다시 인사드립니다."
}

roomId는 채팅방 id, authorId는 보내는이, message는 작성하고 싶은 메세지를 적어주면 된다.

그리고 send를 눌러준다.

send를 눌러주면(왼쪽) 해당 채팅방을 구독하고 있는 사용자(오른쪽)에게 메세지가 도착하는 것을 확인할 수 있다.

🌈 (2024.06.23) 인증 로직 추가

위의 테스트 과정에서 메시지를 보낼 때 roomId, authorId, 및 message가 Json 형식으로 전송된다.

하지만 실제로 메시지를 이렇게 전송하면 authorId는 로그인한 사용자가 아닌 다른 사용자의 ID로 요청될 수 있기 때문에 보안상 취약하다.

따라서 세션(Session) 또는 JWT(Json Web Token)와 같은 인증 수단이 필요하다.

인증을 통해 메시지를 전송하는 사용자가 실제로 해당 메시지를 보낼 권한이 있는지 확인해야 한다.

이를 통해 메시지 전송 과정에서의 보안성을 높일 수 있다.

필자는 JWT를 사용하여 AccessToken을 발급하고, 이를 HTTP 통신 시 인증 방법으로 사용한다.

새로운 토큰을 발급받는 것보다 기존에 사용하던 액세스 토큰을 사용하는 것이 더 낫다고 판단하여, HTTP 통신때 처럼 요청 헤더에 액세스 토큰을 key:value 형식으로 액세스 토큰을 전달하였다.

그런 다음, 토큰에서 직접 유저 정보를 추출해서 웹 소켓 연결 세션에 저장하여 통신하였다.

그럼 변경된 코드를 살펴보자.

WebSocketMessageBrokerConfigurer

@Configuration
@EnableWebSocketMessageBroker
@RequiredArgsConstructor
public class WebSocketConfig implements WebSocketMessageBrokerConfigurer {

    private final StompHandler stompHandler;

    @Override
    public void registerStompEndpoints(StompEndpointRegistry registry) {

        // socketJs 클라이언트가 WebSocket 핸드셰이크를 하기 위해 연결할 endpoint를 지정할 수 있다.
        registry.addEndpoint("/chat/inbox")
                .setAllowedOriginPatterns("*"); // cors 허용을 위해 꼭 설정해주어야 함. setCredential() 설정시에 AllowedOrigin 과 같이 사용될 경우 오류가 날 수 있으므로 OriginPatterns 설정으로 사용하였음
    }

    @Override
    public void configureMessageBroker(MessageBrokerRegistry registry) {
        // 메모리 기반 메시지 브로커가 해당 api를 구독하고 있는 클라이언트에게 메시지를 전달함
        // to subscriber
        registry.enableSimpleBroker("/sub");

        // 클라이언트로부터 메시지를 받을 api의 prefix를 설정함
        // publish
        registry.setApplicationDestinationPrefixes("/pub");


    }

    @Override
    public void configureClientInboundChannel(ChannelRegistration registration) {
        registration.interceptors(stompHandler);
    }

}

StompHandler

@RequiredArgsConstructor
@Component
@Slf4j
public class StompHandler implements ChannelInterceptor {

    private final JwtService jwtService;

    @Override
    public Message<?> preSend(Message<?> message, MessageChannel channel) {
        StompHeaderAccessor accessor = StompHeaderAccessor.wrap(message);

        if (accessor.getCommand() == StompCommand.CONNECT) {
            String accessToken = accessor.getFirstNativeHeader("Authorization");
            if (!this.validateAccessToken(accessToken)) {
                throw AccessTokenRequiredException.EXCEPTION;
            }
            String id = getUserId(accessToken);
            accessor.addNativeHeader("senderUserId", id);
        }


        return message;
    }

    public String getUserId(String accessToken) {
        try {
            String token = accessToken.trim();
            if (token.startsWith("Bearer ")) {
                token = token.substring(7).trim();
            }
            String id = jwtService.extractUsername(token);
            if (id == null || id.isEmpty()) {
                throw UserTokenExpriedException.EXCEPTION;
            }
            return id;
        } catch (ExpiredJwtException e) {
            log.error("만료된 JWT 토큰: {}", e.getMessage());
            throw UserTokenExpriedException.EXCEPTION;
        } catch (MalformedJwtException e) {
            log.error("잘못된 형식의 JWT 토큰: {}", e.getMessage());
            throw UserTokenExpriedException.EXCEPTION;
        } catch (Exception e) {
            log.error("사용자 ID 추출 중 예기치 않은 오류 발생: {}", e.getMessage());
            throw UserTokenExpriedException.EXCEPTION;
        }
    }

    private boolean validateAccessToken(String accessToken) {
        if (accessToken == null || accessToken.trim().isEmpty()) {
            return false;
        }

        String token = accessToken.trim();
        if (token.startsWith("Bearer ")) {
            token = token.substring(7).trim();
        }

        try {
            Claims claims = jwtService.extractAllClaims(token);
            return true;
        } catch (ExpiredJwtException | MalformedJwtException e) {
            log.error("토큰 검증 실패: {}", e.getMessage());
            return false;
        }
    }
}

WebSocketMessageBrokerConfigurer에 ChannelInterceptor를 구현한 StompHandler가 추가되었다.

configureClientInboundChannel에서는 요청 전에 인터셉터를 설정할 수 있는데, 요청 전에 토큰 검증을 위해 StompHandler를 설정해주었다.

StompHandler에서는 소켓 연결 후 헤더에서 Authorization을 찾고, validateAccessToken으로 유효한 토큰인지 검증한다.

만약 유효하다면 AccessToken에서 userId를 추출하여 accessHeader.addNativeHeader를 사용해 기존 헤더에 userId 정보를 추가해 저장한다.

StompEventListener

@Component
@Slf4j
@RequiredArgsConstructor
public class StompEventListener {

    private final JwtService jwtService;
    private final StompHandler stompHandler;

    @EventListener
    public void handleWebSocketConnectListener(SessionConnectedEvent event) {

        StompHeaderAccessor headerAccessor = StompHeaderAccessor.wrap(event.getMessage());
        String sessionId = headerAccessor.getSessionId();

        log.info("[Connected] websocket session id : {}", sessionId);
    }

    @EventListener(SessionConnectEvent.class)
    public void onApplicationEvent(SessionConnectEvent event) {
        StompHeaderAccessor accessor = StompHeaderAccessor.wrap(event.getMessage());
        String accessToken = accessor.getFirstNativeHeader("Authorization");

        if (accessToken != null && accessToken.startsWith("Bearer ")) {
            // "Bearer " 접두사 제거 및 공백 제거
            accessToken = accessToken.substring(7).trim();

            try {
                if (!jwtService.isTokenExpired(accessToken)) {
                    String id = stompHandler.getUserId(accessToken);
                    accessor.getSessionAttributes().put("senderUserId", id);
                } else {
                    // 토큰이 만료된 경우 로그
                    log.warn("Expired token received");
                }
            } catch (Exception e) {
                // JWT 처리 중 발생한 예외 로그
                log.error("Error processing JWT token", e);
            }
        } else {
            // 유효한 Authorization 헤더가 없는 경우 로그
            log.warn("No valid Authorization header found");
        }
    }

    @EventListener
    public void handleWebSocketDisconnectListener(SessionDisconnectEvent event) {

        StompHeaderAccessor headerAccessor = StompHeaderAccessor.wrap(event.getMessage());
        String sessionId = headerAccessor.getSessionId();

        log.info("[Disconnected] websocket session id : {}", sessionId);
    }
}

더 정확하게 디버깅하기 위해 이벤트 리스너도 추가하였다.

ChatMessageController

@Controller
@RequiredArgsConstructor
@Slf4j
public class ChatMessageController {
    private final ChatMessageService chatMessageService;
    private final SimpMessagingTemplate messagingTemplate;

    @MessageMapping("/message")
    public void sendMessage(ChatDto.ChatMessageDto message, SimpMessageHeaderAccessor accessor) {
        String userId = (String) accessor.getSessionAttributes().get("senderUserId");

        // 실시간으로 방에서 채팅하기
        ChatMessage newChat = chatMessageService.createChatMessage(message, userId);
        log.info("received message: {}", message);

        // 방에 있는 모든 사용자에게 메시지 전송
        messagingTemplate.convertAndSend("/sub/channel/"+message.getRoomId(), newChat);
    }
}

ChatMessageDto

/**
 * 웹소켓 접속시 요청 Dto
 */
@Data
@Builder
@NoArgsConstructor
@AllArgsConstructor
public static class ChatMessageDto {
    private String roomId;
    //private String authorId;
    private String message;

    /* Dto -> Entity */
    public ChatMessage toEntity(String userId) {
        ChatMessage chatMessage = ChatMessage.builder()
                .roomId(roomId)
                .authorId(userId)
                .message(message)
                .createdAt(LocalDateTime.now())
                .build();
        return chatMessage;
    }
}

마지막으로 메세지를 전송하는 컨트롤러에선 연결 세션에서 userId의 정보를 받으면 json으로 요청하지 않아도 세션에서 꺼내와 사용이 가능하다.

🌈 인증 추가 후 APIC로 STOMP 테스트-2

Headers 부분에 Key는 Authorization, Value는 Bearer {AccessToken}을 작성해준다.

Send의 요청 메세지는 authorId를 제외한 roomId와 message를 넣어주었다.

여기서 주의할 점은 Headers에 AccessToken을 설정하려고 하면 위 사진처럼 체크박스가 선택된 채로 Key:Value가 하나 더 나오게 된다.

만약 체크박스 되어있다면 풀어주고 우측에 x 버튼을 눌러 삭제시켜 주자 (빈 Key와 빈 Value로 서버에 요청이 되버러 에러가 발생하니 유의하자)

1:1 채팅이 가능하도록 새 탭을 하나 더 만들어 다른 사용자의 AccessToken을 헤더에 설정해주도록 하자

요청을 보내면 토큰에서 추출된 사용자 ID와 함께 메세지가 전송되고, 상대방에게도 잘 도착한다.

메시지가 정상적으로 송수신되는 것을 확인할 수 있다.

🌱 느낀점

Spring Boot와 STOMP를 사용하여 1:1 채팅 기능을 구현하는 과정에서 실시간 데이터 전송, 메시징 브로커, 컴포넌트 간 분리, 사용자 인증 등 다양한 측면을 경험할 수 있었다.

이번 프로젝트에서는 Spring의 내장 브로커를 사용하였지만 실제 프로덕션 환경에선 외부 메시지 브로커를 사용하는 것이 좋을 것 같다.

이후 RabbitMQ와 같은 외부 메시지 브로커로 고도화하는 작업도 구현해보도록 하자. 🍀

출처

채팅서비스를 구현하며 배워보는 Websocket 원리 (feat. node.js)

Spring Boot WebSocket (2) - 웹소켓 이해하기 _ STOMP로 채팅 고도화 하기

[Stomp] Spring Boot with React 채팅 서버

STOMP와 JWT Token을 활용한 채팅 서버 구축

문제사항

백준 4단계 문제였다.

다익스트라 알고리즘의 대표적인 문제로, 이론부터 알아보자.

'다익스트라' 란?

다익스트라 알고리즘은 최단거리 알고리즘 이다.

특징은 시작점이 주어진다는 점, 음수 간선이 주어지지 않는다는 점이다. (시작점 O, 음수 간선 X)

과정을 살펴보자.

1. 인접 리스트로 그래프 구현하기

• (1)번과 같이 1에서 2로 가는 가중치가 8인 엣지(e), 2에서 5로 가는 가중치가 15인 엣지(e) 등 입력 값이 주어지면 (2)번과 같은 그래프로 표현할 줄 알아야 한다.

• (2)번과 같은 그래프로 표현이 된다면 (3)번과 같이 데이터를 자료구조로 담아 표현할 줄 알아야 한다.

인접 행렬로 구현해도 좋지만 시간 복잡도 측면 N의 크기가 큰 것을 대비해 인접 리스트를 선택해 구현하는 것이 좋다.

2. 최단 거리 배열 초기화하기

• 최단 거리 배열을 만들고, 출발 노드 0 이외 노드 무한으로 초기화한다.

3. 값이 가장 작은 노드 고르기

• 최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다.

• 여기선 값이 0인 출발 노드에서 시작한다.

4. 최단 거리 배열 업데이트하기

• 그래프 구현 시 저장해 놓은 연결 리스트 이용해서 선택된 노드에서 에지 값을 바탕으로 다른 노드 값을 업데이트한다.

• 연결 노드의 최단 거리는 두 값 중 더 작은 값으로 업데이트한다. ( 자료구조는 Queue보다는 PriorityQueue로 구현을 선호, compareTo로 Node 간 거리 비교도 필수이다.)

5. 과정 3~4 반복해 최단 거리 배열 완성하기

• 모든 노드가 처리될 때까지 과정 3~4를 반복한다.

• 과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 배열을 만들어 처리하고, 모든 노드가 선택될 때 까지 반복하면 최단거리 배열이 완성된다.

• 완성된 배열에서 각 인덱스의 값의 뜻은 다음과 같다

  시작 노드에서 1번 노드까지 가는데 걸리는 최단 거리 시작 노드에서 2번 노드까지 가는데 걸리는 최단 거리 시작 노드에서 3번 노드까지 가는데 걸리는 최단 거리 시작 노드에서 4번 노드까지 가는데 걸리는 최단 거리 시작 노드에서 5번 노드까지 가는데 걸리는 최단 거리

알고리즘 분류

1. 그래프 (다익스트라)

코드

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

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

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(br.readLine());

        //인접리스트
        ArrayList<Node>[] grape = new ArrayList[V+1];
        //최단거리배열
        int[] D = new int[V + 1];
        //방문배열
        boolean[] visited = new boolean[V + 1];

        for (int i = 0; i <= V; i++) {
            //인접리스트 배열 초기화
            grape[i] = new ArrayList<>();
            //인덱스 값 무한대로 초기화
            D[i] = Integer.MAX_VALUE;
        }

        for (int i = 1; i <= E; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            grape[u].add(new Node(v, w));
        }

        //다익스트라 -> 우선순위 큐
        PriorityQueue<Node> que = new PriorityQueue<>();
        //시작 정점(출발 노드)의 인덱스 값은 0
        D[K] = 0;
        que.offer(new Node(K, 0));

        while (!que.isEmpty()) {
            Node now = que.poll();
            visited[now.toNode] = true;
            for (Node node : grape[now.toNode]) {
                if (!visited[node.toNode]) {
                    if (D[now.toNode] + node.e < D[node.toNode]) {
                        D[node.toNode] = D[now.toNode] + node.e;
                        que.offer(new Node(node.toNode, D[node.toNode]));
                    }
                }
            }
         }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            if (D[i] == Integer.MAX_VALUE) {
                sb.append("INF").append("\n");
            } else {
                sb.append(D[i]).append("\n");
            }
        }
        System.out.println(sb);
    }

    static class Node implements Comparable<Node>{
        int toNode;
        int e;

        @Override
        public int compareTo(Node o){
            return this.e - o.e;
        }

        public Node(int toNode, int e) {
            this.toNode = toNode;
            this.e = e;
        }
    }
}

문제사항

플래티넘 5단계 문제였다.

앞서 포스팅한 [백준] 2252번 줄 세우기 (JAVA), [백준] 1516번 게임 개발 (JAVA) 문제도 위상 정렬 문제였는데, 해당 문제도 위상 정렬 알고리즘을 이용한 문제이다.

여기서 말하는 모든 사람이 만나는 시간은 최장시간이며 도착도시의 최대비용을 구하면 된다.

그리고 1분도 쉬지 않고 달려야하는 도로의 수는 최대값을 만드는 경로(=모든 사람이 만나는 시간)의 수와 같다.

출발하는 도시와 도착하는 도시가 지정되기 때문에 목적에 따라 큐에 넣는 노드를 다르게 해주어야 한다.

일반적인 위상정렬 문제라고 생각하면 안되는게, 1분도 쉬지 않고 달려야 하는 도로의 개수를 구하는 데에는 역방향 그래프에서 위상정렬을 수행해야 한다는 점이다.

따라서 정방향 그래프와 역방향 그래프를 만들어주었다. 정방향 그래프에서는 시작도시를 출발점으로 정하여 위상정렬을 수행한다. 여기서 임계경로(path[])는 각 노드에서 도착 도시까지의 도달하는데 걸리는 최대 시간을 말한다.

그러므로 모든 사람이 만나는 시간은 마지막 노드의 임계경로 값이다.

정방향 그래프에서 임계경로를 모두 설정해주면, 역방향 그래프에서도 위상정렬 수행이 가능하도록 구현하였다. 이때 역방향 그래프에서 정방향에서 수행했던 도착도시가 시작점이 된다.

여기서 한 정점까지 소모한 비용 + 도착 도시까지의 최대 비용(=임계경로)를 더해주는 경우를 cnt로 카운팅해주었다.

추가로 역방향 그래프에서 방문한 노드는 다시 방문할 수 없도록, 방문 배열을 선언하여 구분해주는 작업은 필수로 들어가야 한다. (중복 카운팅됨)

path[도착도시]와 cnt를 출력하면 된다.

알고리즘 분류

1. 그래프 (위상 정렬)

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        ArrayList<ArrayList<Node>> graph = new ArrayList<>(); // 정방향 그래프
        ArrayList<ArrayList<Node>> reverse_graph = new ArrayList<>(); // 역방향 그래프

        for (int i = 0; i <= n; i++) { //크기 +1만큼은 더 크게 해줘야함 (i<=n)
            graph.add(new ArrayList<Node>());
            reverse_graph.add(new ArrayList<Node>());
        }
        // 진입차수 저장 배열
        int[] indegree = new int[n + 1];
        // 각 출발 도시(시작노드)부터 도착 도시(마지막노드)까지 임계경로(최대시간)
        int[] path = new int[n + 1];
        StringTokenizer st;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            //정방향: a->b, a에서 b까지의 가중치 = e
            graph.get(a).add(new Node(b, e));
            //다음 노드를 진입차수 대상으로 두고 +1
            indegree[b]++;
            //역방향: b->a, b에서 a까지의 가중치 = e
            reverse_graph.get(b).add(new Node(a, e));
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        //위상정렬
        Queue<Integer> que = new LinkedList<>();
        que.offer(start);
        while (!que.isEmpty()) {
            int now = que.poll();
            for (Node node : graph.get(now)) {
                //다음 노드를 진입차수 대상으로 두고 -1
                indegree[node.toNode]--;
                //동일 노드에 간선이 둘 이상이면(=진입차수가 0보다 큰 경우) Math.max 작용 (큰값 대입)
                path[node.toNode] = Math.max(path[node.toNode], path[now] + node.e);
                //진입차수가 0이면 que에 추가
                if (indegree[node.toNode] == 0) {
                    que.offer(node.toNode);
                }
            }
        }

        // 역위상정렬
        que.offer(end);
        int cnt = 0;
        boolean[] visited = new boolean[n + 1];
        visited[end] = true;
        while (!que.isEmpty()) {
            int now = que.poll();
            for (Node node : reverse_graph.get(now)) {
                //도달 정점에서의 최대 비용 + 간선에서 소모한 비용 = 최대 비용(고정 값일 것)
                if (path[now] == path[node.toNode] + node.e) {
                    cnt++;
                    if (!visited[node.toNode]) {
                        que.offer(node.toNode);
                        visited[node.toNode] = true;
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(path[end]).append("\n");
        sb.append(cnt);
        System.out.println(sb);
    }

    static class Node {
        int toNode; // 다음 노드
        int e; // 현재 노드와 다음 노드 간의 간선의 가중치

        public Node(int toNode, int e) {
            this.toNode = toNode;
            this.e = e;
        }
    }
}

출처

[백준 1948] 임계경로 (JAVA)