너비 우선 탐색(BFS)

BFS(breadth-first search)는 시작노드에서 출발해 시작노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

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

핵심이론

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
   BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않기 때문에 방문한 노드를 체크하기 위한 배열이 필요하다.
   차이점이 있다면 탐색을 위해 스택이 아닌 큐를 사용하는 것이다.

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

3. 큐 자료구조에 값이 없을 때까지 반복하기
   앞선 과정을 반복한다. 선입선출 방식으로 탐색하므로 탐색 순서가 DFS와 다름을 확인해보자.

탐색

탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘을 말한다.
주어진 데이터의 성질(정렬 혹은 비정렬)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요하다.

깊이 우선 탐색(DFS)

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

재귀함수로 구현 시 스택 오버플로(stack overflow)에 유의해서 구현해야 한다. 하지만 스택보다는 스택의 성질을 가진 재귀 함수로 많이 구현하는 편이다.
응용해서 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.

핵심 이론

DFS는 한번 방문한 노드를 다시 방문하면 안되서 노드 방문 여부를 체크할 배열이 필요하다.
그래프는 인접 리스트로 표현하고 탐색 방식은 후입선출 특성을 가지므로 스택을 사용해서 알아보자.

DFS를 위해 필요한 초기 작업

• 인접 리스트로 그래프 표현하기
• 방문 배열 초기화하기
• 시작 노드 스택에 삽입하기

1. DFS를 사용할 노드를 정한 후 사용할 자료구조 초기화하기

스택에 시작 노드를 1로 삽입할 때 해당 위치의 방문 배열을 체크하면 T,F,F,F,F 가 된다.

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

pop을 수행하여 노드를 꺼낸다. 꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하여 방문 배열을 체크한다.
방문 배열은 T,T,T,F,F,F 가 된다.

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

1
2
3
4
5
6

list[0] = [2,3];
list[1] = [5,6];
list[2] = [4];
list[3] = [6];
list[4]
list[5]

스택에서 3을 꺼내며 탐색 순서에 기록하고 인접 노드 4를 스택에 삽입하고 방문 배열에 체크한다.
스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하여 살펴본다.

그래프

그래프는 노드와 엣지로 구성된 집합이다. 노드는 데이터를 표현하는 단위이고 엣지는 노드를 연결한다.

엣지 리스트

엣지를 중심으로 그래프를 표현한다. 배열에 출발 노드, 도착 노드를 저장하여 엣지를 표현하는데 여기에 가중치를 표함하는 경우도 있다.

1. 엣지 리스트로 가중치가 없는 그래프 표현

가중치가 없다면 출발 노드와 도착 노드만 표현하니까 배열의 행은 2개면 충분하다.

1
2
3
4
5
6

[1,2]
[1,3]
[3,4]
[2,4]
[2,5]
[4,5]

1 -> 2 로 나가는 엣지를 [1,2] 로 표현한다. 이렇게 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현한다.
노드를 배열에 저장하여 엣지를 표현하니까 엣지 리스트라고 부른다.
(방향이 없는 그래프라면 [1,2]와 [2,1]은 같은 표현이 될 수 있다.)

1. 엣지 리스트로 가중치가 있는 그래프 표현

가중치가 있으면 행을 3개로 늘려서 3번째 행에 가중치를 저장하면 된다.

1
2
3
4
5
6

[1,2,8],
[1,3,3],
[3,4,13],
[2,4,4],
[2,5,15],
[4,5,2]

1 -> 2 로 나가는 엣지의 가중치는 8이라서 [1,2,8] 로 표현한다. 엣지 리스트 자체는 구현하기 쉽지만 특정 노드와 관련된 엣지를 탐색하기에 쉽지 않다.
엣지 리스튼 보통 벨만 포드나 크루스칼(MST) 알고리즘에서 사용되며 노드 중심 알고리즘에선 잘 안쓰인다.

인접 행렬

2차원 배열을 자료구조로 이용하여 그래프를 표현한다.
인접행렬은 엣지 리스트와 다르게 노드 중심으로 그래프를 표현한다.

1. 인접 행렬로 가중치가 없는 그래프 표현

1
2
3
4
5

[0,1,1,0,0],
[0,0,0,1,1],
[0,0,0,1,0],
[0,0,0,0,1],
[0,0,0,0,0]

1 -> 2 로 향하는 엣지를 인접 행렬은 1행 2열에 1을 저장하는 방식으로 표현한다.
가중치가 없어서 1을 저장하며 엣지가 있다는 표시를 노드 중심으로 한다고 이해하면 편하다.

2. 인접 행렬로 가중치가 있는 그래프 표현
   가중치가 없을때 1로 저장하던 2차원 배열에 가중치에 따른 값을 저장하면 된다.

1
2
3
4
5

[0,8,3,0,0],
[0,0,0,4,15],
[0,0,0,13,0],
[0,0,0,0,2],
[0,0,0,0,0]

인접 행렬을 이용한 그래프 구현은 쉽다. 두 노드를 연결하는 엣지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있는 장점이 있다.
하지만 노드와 관련된 엣지를 탐색하려면 N번 접근해야하므로 노드 갯수에 비해 엣지가 적을 때는 공간 효율성이 떨어진다.

또한 노드 갯수가 많은 경우 아예 2차원 배열 선언 자체를 할 수 없는 결함도 있다. 예를 들어 노드가 3만개가 넘어가면 자바에서 힙스페이스 에러가 발생한다.
인접 행렬은 노드 개수에 따라 사용 여부를 적절하게 판단하는 능력도 필요하다.

인접 리스트

ArrayList로 그래프를 표현한다. 노드 갯수만큼 ArrayList를 선언하는데 자료형은 경우에 맞게 사용한다.

1. 인접 리스트로 가중치 없는 그래프 표현
   N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 갯수만큼 배열을 연결하는 방식으로 표현

1
2
3
4
5
6
7

// ArrayList<Integer>[5] 로 선언

list[0] = [2,3];
list[1] = [4,5];
list[2] = [4];
list[3] = [5];
list[4]

노드1과 연결된 2,3 녿드는 ArrayList[1]에 [2,3]을 연결하는 방식으로 표현한다.

2. 인접 리스트로 가중치가 있는 그래프 표현
   가중치가 있을 경우 자료형을 클래스로 사용한다. 예를 들어 (도착노드, 가중치)를 갖는 Node 클래스를 선언하여 ArrayList에 사용한다.

1
2
3
4
5

list[0] = [[2,8],[3,3]];
list[1] = [[4,4],[5,15]];
list[2] = [[4,13]];
list[3] = [[5,2]];
list[4]

ArrayList[1]에 [(2,8), (3,3)] 이 연결되어 있다. 이는 노드1과 가중치8 엣지로 노드 1과 3이 가중치 3 엣지로 연결되어 있다는 걸 보여주고 방향성도 알수 있다.
인접 리스트를 이용한 그래프 구현은 다른 방법들에 비해 복잡한 편이지만
노드와 연결되어 있는 엣지를 탐색하는 시간은 뛰어나며, 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않는다.
그래서 많은 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호한다.

Spring에서 Event

Spring은 일반적으로 DI를 통해 메서드를 호출하여 데이터를 전달한다.

규모가 작을 때는 큰 문제가 없지만 도메인이 점점 복잡히질 경우 여러 도메인 사이에 강한 의존성 결합으로 시스템이 복잡해지는 문제가 발생할 수 있다.

Spring은 Event를 통해 Bean과 Bean 사이의 데이터를 전달할 수 있는데 ApplicationContext에 이벤트를 넘겨주면 Listener에서 받아서 처리한다.

이벤트를 발생시키는 publisher와 받아서 처리하는 Listener, 전달할 데이터를 가지고 있는 event클래스로 구성된다.

ApplicationEventPublisher

Spring의 ApplicationContext가 상속하는 인터페이스 중 하나로 옵저버 패턴의 구현체이다.

Publisher와 Listener를 Spring의 Bean으로 등록하고 publishEvent()가 실행되면 등록된 listener에 Event를 던진다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

@Getter
@Builder
public class TestEvent {
    private String eventId;
    private String type;
    private String data;

    public static TestEvent toCompleteEvent(String data){
        return TestEvent.builder()
                .eventId(UUID.randomUUID().toString())
                .type("completed")
                .data(data)
                .build();
    }

    public static TestEvent toErrorEvent(){
        return TestEvent.builder()
                .eventId(UUID.randomUUID().toString())
                .type("error")
                .data("data is Null")
                .build();
    }
}

Spring 4.2 부터는 ApplicationEvent를 상속받지 않아도 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

@Slf4j
@Service
@RequiredArgsConstructor
public class EventTestService {
    private final ApplicationEventPublisher applicationEventPublisher;

    public Mono<String> publishTest(String message) {
        return Mono.fromCallable(() -> {
            if(message != null){
                applicationEventPublisher.publishEvent(TestEvent.toCompleteEvent(message));
            } else {
                applicationEventPublisher.publishEvent(TestEvent.toErrorEvent());
            }

            return "result: " + message;
        });
    }
}

ApplicationContext를 주입받아도 되지만 명시적으로 ApplicationEventPublisher를 주입받아서 사용한다.

1
2
3
4
5
6
7
8
9
10

@Slf4j
@Component
public class TestEventListener {

    @EventListener
    public void onTestEventHandle(TestEvent event) {
        log.info("event Id: " + event.getEventId() + ", type: " + event.getType() + ", Message: " + event.getData());
        log.info("Handling context started event.");
    }
}

Spring Bean에 등록된 EventListener에서 이벤트를 받아서 처리한다.

1
2

2023-01-19 15:26:28.072  INFO 20172 --- [ctor-http-nio-3] c.e.s.listener.TestEventListener         : event Id: 8f9d4534-7ada-404a-9b1b-71f2958a749b, type: completed, Message: testSample!
2023-01-19 15:26:28.072  INFO 20172 --- [ctor-http-nio-3] c.e.s.listener.TestEventListener         : Handling context started event.

잘 돌아간다.

Spring에서 Bean들은 Spring Container에 의해서 싱글톤으로 관리되는데 이는 애플리케이션에 한개의 인스턴스만 존재하는데 여러 Thread가 동시에 접근할 경우 동시성 이슈가 발생할 수 있는데 이를 해결하기 위해 Java에서는 ThreadLocal 객체를 활용할 수 있다.

ThreadLocal은 Thread만 접근가능한 저장소로 여러 Thread가 접근할 경우 각각의 Thread를 식별해서 저장소를 구분한다. 따라서 같은 인스턴스의 ThreadLocal 필드에 여러 Thread가 접근하더라도 상관이 없다.

get(), set(), remove() 같은 메서드를 통해 조회, 저장, 저장소를 초기화한다.

톰캣과 같은 WAS에선 Thread Pool을 만들고 Request가 들어오면 각 Thread가 해당 요청을 담당하여 프로세스를 처리한다.

Spring Boot가 실행되면 내부적으로 ThreadPoolExecutor 구현체를 생성해서 내장 톰캣이 사용할 Thread Pool을 생성하는 구조
Thread Pool 을 사용하는 환경에선 Thread Pool을 통해 Thread가 재사용될 수 있으므로 사용이 끝나면 명시적으로 초기화를 해줘야 한다.
ThreadPoolExecutor를 확장해서 beforeExecute()와 afterExecute() 메서드에서 이러한 문제들을 해결할 수 있다.
기존 서블릿 기반의 Spring Boot는 Tomcat을 기본 Embeded WAS로 사용하는데 WebFlux의 경우 Netty를 기본으로 사용한다.

Tomcat은 요청 당 하나의 Thread가 동작하지만 Netty는 1개의 이벤트를 받는 Thread와 다수의 Worker Thread로 동작하게 된다.
Netty는 channel에서 발생하는 이벤트를 EventLoop가 처리하는 구조로 동작하는데 EventLoop는 이벤트를 실행하기 위한 무한루프 Thread라고 볼수 있다.

Netty에 대한 자세한 내용은 다음에 더 찾아보자.

아래는 webFlux에서 ThreadLocal에 저장하던 데이터를 어떻게 보관하는지 찾아본 글 내용이 흥미로워서 나중에 보려고 추가함
https://sightstudio.tistory.com/15