이 프로젝트는 스레드가 4개로 제한된 환경에서 돌아간다. 이 제약이 프로젝트 전체의 설계에 영향을 줬다. 세마포어 permit을 4로 잡은 것도, 트랜잭션을 쪼갠 것도, Rate Limiter를 건 것도 결국 이 4개라는 제약에서 출발한 거다.

그런데 "스레드 4개"라는 말이 정확히 무슨 말인지, 왜 4개인지, 이게 어떤 의미인지를 정리해둔다.

프로세스 vs 스레드

먼저 기본부터 정리하자.

프로세스

실행 중인 프로그램 하나다. OS로부터 독립된 메모리 공간을 할당받는다. 코드 영역, 데이터 영역, 힙, 스택이 모두 독립적이다. 프로세스 간에는 메모리를 공유하지 않는다. 통신하려면 IPC(Inter-Process Communication)를 써야 한다.

스레드

프로세스 안에서 실행되는 가벼운 실행 단위다. 같은 프로세스의 스레드들은 힙 메모리를 공유한다. 코드 영역도 공유한다. 각 스레드는 자체 스택만 가진다.

[프로세스]
├─ 코드 영역 (공유)
├─ 힙 영역 (공유)
├─ 스레드 A: [자체 스택]
├─ 스레드 B: [자체 스택]
├─ 스레드 C: [자체 스택]
└─ 스레드 D: [자체 스택]

힙을 공유하니까 스레드 간 데이터 교환이 빠르다. 대신 동시에 같은 데이터를 수정하면 경직 상태(race condition)가 생길 수 있다. 그래서 동기화가 필요한 거고, 세마포어나 Lock을 쓰는 거다.

컨텍스트 스위칭

OS가 스레드를 교체할 때 발생한다. 현재 스레드의 상태(레지스터 값, 프로그램 카운터 등)를 저장하고, 다음 스레드의 상태를 복원하는 과정이다.

스레드 간 스위칭은 프로세스 간 스위칭보다 가볍다. 프로세스 간에는 메모리 공간 전체를 교체해야 하지만, 스레드 간에는 스택과 레지스터만 교체하면 된다. 그래도 비용이 0은 아니다. 앞에서 fair 세마포어를 안 쓴 이유 중 하나가 이 컨텍스트 스위칭 비용이었다.

스레드 풀

내 프로젝트에서 "스레드 4개"라는 건 톰캣의 스레드 풀 설정이다. Spring Boot는 기본적으로 내장 톰캣을 쓰고, 톰캣의 기본 스레드 수는 200이다. 근데 프리티어 호스팅 환경에서는 리소스 제한으로 이게 4개로 제한되어 있었다.

스레드 풀이 필요한 이유는 간단하다. 요청마다 스레드를 새로 만들면 생성/소멸 비용이 크다. 미리 스레드를 만들어두고 재사용하는 게 스레드 풀이다.

[스레드 풀: 4개]
├─ 스레드 1: 요청 A 처리 중
├─ 스레드 2: 요청 B 처리 중
├─ 스레드 3: 요청 C 처리 중
└─ 스레드 4: 요청 D 처리 중

요청 E 들어옴 → 대기 (스레드가 비어야 처리 가능)

4개뿐이라는 게 모든 문제의 출발점이었다. 트랜잭션이 30초씩 걸리면 4개가 전부 물리고, 다른 요청은 아무것도 못 하고 대기한다. 이게 앞에서 트랜잭션을 쪼갤 수밖에 없었던 이유다.

블로킹 vs 논블로킹

스레드가 4개인 환경에서 LLM 호출이 블로킹 I/O라는 게 핵심 문제였다. 이 부분을 정리한다.

블로킹 I/O

I/O 작업(네트워크 호출, 파일 읽기 등)이 완료될 때까지 스레드가 멈춘다. 아무것도 안 하고 기다린다. CPU를 쓰지 않는데 스레드를 점유하고 있는 거다.

스레드 1: [LLM 호출] ─── 대기 중 (5초) ─── [응답 수신]
             ↑ 이 5초 동안 스레드는 아무것도 못 함

LLM 호출이 5초 걸리면 스레드가 5초간 낭비된다. 스레드가 4개인데 전부 LLM 호출에 빠져 있으면, 다른 요청은 버튼 누르는 것조차 처리 못 한다.

논블로킹 I/O

I/O 작업을 요청하고 바로 다음 작업을 수행한다. I/O가 완료되면 콜백으로 결과를 받는다. 스레드가 낭비되지 않는다.

스레드 1: [LLM 호출 요청] → [다른 작업 수행] → ... → [콜백으로 응답 처리]
             ↑ 스레드가 안 낭비됨

내 프로젝트에서의 판단

현재는 블로킹 I/O로 동작한다. Spring MVC + RestTemplate 기반이라 기본적으로 블로킹이다.

논블로킹으로 바꾸려면 Spring WebFlux + WebClient를 쓰거나, Kotlin 코루틴을 도입해야 한다. 이러면 스레드가 I/O 대기 중에 다른 요청을 처리할 수 있어서, 4개의 스레드로도 훨씬 많은 동시 요청을 처리할 수 있다.

그럼 왜 논블로킹으로 안 바꿨나? 고민했다.

하나, 기존 코드베이스가 전부 Spring MVC 기반이다. WebFlux로 전환하려면 서비스 레이어부터 리팩토링해야 한다. 규모가 크다.

둘, 리액티브 프로그래밍의 학습 곡선이 있다. Mono, Flux, subscribe 같은 개념을 새로 익혀야 한다.

셋, 지금 규모에서는 트랜잭션 분리만으로도 커넥션 점유 문제가 해결됐다. 30초가 2~3초로 줄었으니까.

결론적으로, 블로킹이라는 한계는 인지하고 있지만 현재 단계에서는 트랜잭션 분리로 충분히 해결됐다고 판단했다. 사용자가 늘어서 스레드 4개로 감당이 안 되는 시점이 오면, 그때 WebFlux나 코루틴 도입을 고려할 거다.

k6로 검증한 이야기

세마포어, Rate Limiter, 트랜잭션 분리까지 적용한 후에 "진짜로 되는가?"를 확인해야 했다. 그래서 k6로 부하 테스트를 돌렸다.

k6가 뭐냐

Grafana에서 만든 오픈소스 부하 테스트 도구다. JavaScript로 시나리오를 작성하고, 가상 사용자(VU, Virtual User)를 만들어서 서버에 부하를 준다.

import http from 'k6/http';
import { check, sleep } from 'k6';

export const options = {
  stages: [
    { duration: '30s', target: 4 },   // 30초에 걸쳐 VU 4명까지 증가
    { duration: '1m', target: 4 },    // 1분간 VU 4명 유지
    { duration: '30s', target: 10 },  // 30초에 걸쳐 VU 10명으로 증가
    { duration: '1m', target: 10 },   // 1분간 VU 10명 유지
    { duration: '30s', target: 0 },   // 30초에 걸쳐 0으로 감소
  ],
};

export default function () {
  const res = http.post('http://localhost:8080/api/game/session');
  check(res, {
    'status is 200': (r) => r.status === 200,
    'status is not 429': (r) => r.status !== 429,
  });
  sleep(1);
}

테스트 시나리오 유형

부하 테스트에는 목적에 따라 다른 시나리오가 있다.

Smoke Test

최소한의 부하로 기본 동작을 확인한다. VU 1~2명으로 짧게 돌린다. "일단 된다"를 확인하는 것이다.

Load Test

예상 트래픽을 시뮬레이션한다. 내 프로젝트는 동시 사용자 4명 정도를 예상했으니까 VU 4명이 Load Test의 기준이 된다.

Stress Test

예상을 넘어서는 부하를 줘서 한계점을 찾는다. VU를 점점 늘려서 언제부터 에러가 터지는지, 응답시간이 급격히 느려지는지를 확인한다.

Spike Test

갑작스러운 트래픽 급증을 시뮬레이션한다. VU를 0에서 갑자기 10으로 올려서 서버가 어떻게 반응하는지 본다.

내가 측정한 것들

테스트에서 중요하게 본 지표들이다.

429 에러 발생률

가장 중요한 지표였다. 이중 방어 적용 전 80%, 적용 후 10% 이내.

응답 시간 (p50, p95, p99)

평균은 의미 없다. 왜 그러냐면, 요청 100개 중 99개가 1초이고 1개가 100초이면 평균은 약 2초다. 답이 2초만 걸리는 것처럼 보이지만, 실제로는 1명이 100초를 기다린 거다.

그래서 백분위수를 본다.

p50: 중앙값. 요청의 절반이 이 시간 이내에 끝난다.

p95: 요청의 95%가 이 시간 이내에 끝난다. 대부분의 사용자 경험을 나타낸다.

p99: 요청의 99%가 이 시간 이내에 끝난다. 극단적 지연을 보여준다.

보통 p95를 기준으로 성능을 판단한다. 내 프로젝트에서는 트랜잭션 분리 전후의 p95 응답시간 변화를 확인하는 게 핵심이었다.

동시 접속 시 에러율

VU를 늘려서 언제부터 에러가 터지기 시작하는지. 세마포어와 Rate Limiter가 제대로 동작하는지 확인할 수 있었다.

테스트에서 발견한 것

k6를 돌리면서 동시성 제어의 동작을 확인했는데, 예상치 못한 문제도 발견했다.

로그를 분석해보니 단서 생성 validation에서 invalid value가 80% 이상의 확률로 발생하고 있었다. LLM이 생성한 단서가 검증을 통과하지 못하는 거다.

이건 동시성 문제가 아니라 LLM 응답 품질 문제였다. 단서 수와 방 수가 너무 많아서 LLM이 제대로 된 형식의 응답을 못 만들어내고 있었다.

해결은 두 가지를 했다. 단서 수와 방 수를 과감히 줄였고, 단서에 힌트를 넣도록 프롬프트를 수정했다. "난이도가 너무 어렵다"는 사용자 피드백과도 맞닿는 부분이었다.

성능 테스트를 돌리다가 성능과 상관없는 품질 문제를 발견한 건데, 이게 테스트의 가치라고 생각한다. 예상한 것만 확인하는 게 아니라, 예상하지 못한 것을 발견하는 것.

5개 글을 마무리하며

이 시리즈 전체를 통해서 하고 싶었던 말은 이거다.

RPM 4, 스레드 4개라는 제약 속에서 문제를 만났고, 각 문제에 대해 "왜 이게 문제인지", "어떤 선택지가 있는지", "왜 이걸 선택했는지", "다른 걸 선택했으면 어떘을지"를 고민했다.

세마포어를 골랐을 때 synchronized와 ReentrantLock을 왜 버렸는지 알고 있다. Guava Rate Limiter를 골랐을 때 Redis를 왜 안 썼는지 알고 있다. 트랜잭션을 나눴을 때 Atomicity를 포기한 대신 뭘 얻었는지 알고 있다. 서킷 브레이커를 안 쓴 이유도, 논블로킹으로 안 바꾼 이유도 알고 있다.

"쓴 것"보다 "안 쓴 것"에 대한 이유가 더 중요하다고 생각한다. 기술을 도입하는 건 누구나 할 수 있지만, 안 도입한 근거를 말할 수 있는 건 그 기술을 이해하고 있다는 증거니까!!!

이 프로젝트에서 LLM은 외부 API다. 내가 제어할 수 없는 영역이다. 언제 응답이 올지, 얼마나 걸릴지, 실패할지 성공할지 모두 내 손 밖이다.

세마포어와 Rate Limiter로 RPM 초과를 막고, 트랜잭션을 쪼개서 커넥션 점유 시간을 줄였다. 그런데 그것만으로는 외부 API 호출의 불안정성 자체를 해결한 게 아니다. LLM이 5초 만에 응답할 수도, 30초가 걸릴 수도, 아예 응답이 안 올 수도 있다.

이 글에서는 외부 API를 호출할 때 반드시 고려해야 하는 것들을 정리한다.

타임아웃 — 무한정 기다리면 안 된다

외부 API를 호출할 때 가장 기본적으로 해야 할 것이 타임아웃 설정이다. 설정 안 하면 어떻게 될까? LLM 서버가 응답을 안 보내면 내 서버는 무한정 기다린다. 스레드가 물려버리는 거다.

타임아웃은 두 종류가 있다.

Connection Timeout

서버와 TCP 연결을 유지하는 데 걸리는 최대 시간이다. 상대 서버가 아예 응답을 안 하거나, 네트워크에 문제가 있을 때 걸린다.

일반적으로 3~5초 정도가 적절하다. 연결 자체가 5초 이상 걸린다면 상대 서버에 문제가 있는 거니까 기다려봤자 의미가 없다.

Read Timeout

연결은 됐는데, 응답 데이터를 다 받는 데 걸리는 최대 시간이다. LLM 호출의 경우 이게 중요하다. LLM은 응답 생성에 수 초에서 수십 초가 걸릴 수 있으니까.

내 프로젝트 기준으로 LLM 응답이 보통 3~10초 사이였다. 그래서 Read Timeout을 너무 짧게 잡으면 정상 응답도 끊어버리고, 너무 길게 잡으면 스레드가 오래 물린다. 적절한 균형점을 찾아야 한다.

// RestTemplate 예시
SimpleClientHttpRequestFactory factory = new SimpleClientHttpRequestFactory();
factory.setConnectTimeout(5000);  // 5초
factory.setReadTimeout(15000);    // 15초

이걸 설정 안 하는 것과 하는 것의 차이는 엄청나다. 설정 안 하면 스레드가 영원히 락업될 수 있다. 설정하면 최소한 "포기하고 다음 요청을 처리할 수 있다."

재시도(Retry) 전략

타임아웃이 발생하거나 LLM이 에러를 리턴하면, 다시 시도해야 한다. 근데 재시도를 어떻게 하느냐에 따라 결과가 크게 달라진다.

단순 재시도 (Immediate Retry)

실패하면 즉시 다시 시도한다.

실패 → 재시도 → 실패 → 재시도 → 실패 → 포기

문제는 서버가 과부하 상태에서 실패한 건데, 즉시 다시 때리면 과부하를 악화시킨다는 것이다. 특히 429 에러(RPM 초과)는 "너무 많이 보냈다"는 의미인데, 바로 다시 보내면 또 429가 나올 것이다.

지수 백오프 (Exponential Backoff)

재시도 간격을 점점 늘리는 전략이다.

1차 시도: 실패 → 1초 대기
2차 시도: 실패 → 2초 대기
3차 시도: 실패 → 4초 대기
4차 시도: 실패 → 8초 대기
...
최대 재시도 횟수 도달 → 포기

서버에 회복할 시간을 주는 거다. AWS, Google Cloud, 대부분의 API 서비스들이 이 방식을 권장한다.

지수 백오프 + Jitter

여기에 랜덤 지연(jitter)을 추가한다.

1차: 1초 + random(0~500ms)
2차: 2초 + random(0~500ms)
3차: 4초 + random(0~500ms)

왜 jitter가 필요하냐면, 여러 클라이언트가 동시에 실패하면 동시에 재시도한다. 지수 백오프만 쓰면 동시에 1초 뒤에, 동시에 2초 뒤에 때린다. 이걸 Thundering Herd 라고 한다. jitter를 추가하면 재시도 시점이 분산된다.

내 프로젝트에서의 선택

RPM이 4인 환경이라 Thundering Herd가 발생할 규모는 아니었다. 하지만 단순 재시도는 429 에러를 악화시키니까 지수 백오프는 적용했다. jitter까지 가진 않았던 건, 동시 사용자 수가 적어서 재시도 충돌 가능성이 낮았기 때문이다. 스케일이 커지면 jitter도 추가해야 한다.

HTTP 상태 코드 — 에러마다 대응이 다르다

LLM API에서 돌아오는 에러는 종류가 다양하다. 각각 대응이 다르다.

429 Too Many Requests

RPM 초과. 재시도 가능하지만, 바로 재시도하면 또 429가 나온다. 지수 백오프로 간격을 두고 재시도해야 한다. 내 프로젝트에서 가장 많이 만난 에러다.

408 Request Timeout

서버가 요청을 처리하는 데 너무 오래 걸림. 재시도 가능하다.

500 Internal Server Error

서버 내부 오류. 재시도해볼 수 있지만, 서버 자체의 문제라 성공 보장이 없다.

503 Service Unavailable

서버가 일시적으로 이용 불가. 재시도 가능하지만 간격을 두어야 한다.

400 Bad Request

내가 보낸 요청이 잘못된 것. 재시도해도 의미 없다. 요청을 고쳐야 한다.

401/403 Unauthorized/Forbidden

인증 문제. 재시도 의미 없다. API 키를 확인해야 한다.

정리하면 이렇다:

모든 에러를 똑같이 재시도하면 안 된다. 400 에러를 재시도하면 계속 400이 나오는 거니까 의미 없는 호출만 쌓인다. 에러 종류에 따라 대응을 분기해야 한다.

서킷 브레이커 패턴 — 끊을 줄도 알아야 한다

재시도만으로는 해결 안 되는 상황이 있다. LLM API가 지속적으로 실패하는 경우다. 이럴 때 계속 호출하면 내 서버 리소스만 낭비한다.

이럴 때 쓰는 게 서킷 브레이커(Circuit Breaker) 패턴이다. 전기 회로의 차단기에서 따온 개념이다.

동작 원리

세 가지 상태가 있다:

CLOSED (정상)

요청이 정상적으로 통과한다. 실패가 누적되면 OPEN으로 전환된다.

OPEN (차단)

요청을 아예 보내지 않는다. 즉시 실패 응답을 리턴한다. 일정 시간 후 HALF_OPEN으로 전환된다.

HALF_OPEN (테스트)

제한된 수의 요청만 통과시켜서 테스트한다. 성공하면 CLOSED로, 실패하면 다시 OPEN으로.

[CLOSED] ── 실패 누적 ──▶ [OPEN] ── 시간 경과 ──▶ [HALF_OPEN]
    ▲                                                    │
    └─────── 성공 ────────────────────────────┘
                                              │
                  [OPEN] ◀── 실패 ─────┘

라이브러리

Java에서는 Resilience4j가 대표적이다.

CircuitBreakerConfig config = CircuitBreakerConfig.custom()
    .failureRateThreshold(50)        // 실패률 50% 이상이면 OPEN
    .waitDurationInOpenState(Duration.ofSeconds(30))  // 30초 후 HALF_OPEN
    .slidingWindowSize(10)           // 최근 10개 요청 기준
    .build();

CircuitBreaker circuitBreaker = CircuitBreaker.of("llmApi", config);

String result = circuitBreaker.executeSupplier(() -> callLLMApi());

Netflix Hystrix도 유명하지만 이제 더 이상 유지보수되지 않는다. Resilience4j가 현재 표준이다.

내 프로젝트에서는

서킷 브레이커를 직접 적용하지는 않았다. 이유는 두 가지다.

하나, 이미 세마포어 + Rate Limiter로 429 에러를 10% 이내로 떨궜다. 지속적 실패가 발생할 상황이 많지 않았다.

둘, 프로젝트 규모상 라이브러리를 하나 더 도입하는 복잡도가 얻는 이익대비 크다고 판단했다.

다만 어떤 것이고 왜 필요한지는 알고 있다. 프리티어를 쓰지 않게 되거나 트래픽이 늘어나면 그때는 도입해야 한다. 특히 LLM API가 장시간 장애를 일으키는 상황에서는 서킷 브레이커 없이는 사용자 경험이 극도로 나빠진다. 요청할 때마다 느리게 실패하는 것보다, 빠르게 "지금은 안 된다"고 알려주는 게 낫다.

전체 방어 구조 정리

내 프로젝트에서 외부 API 호출에 대한 방어를 정리하면 이렇다:

요청 들어옴
  │
  ├─ [1차 방어] Semaphore: 동시 4개 제한
  │
  ├─ [2차 방어] Rate Limiter: 분당 4회 속도 제한
  │
  ├─ [3차 방어] Timeout: 연결 5초 / 응답 15초
  │
  ├─ [4차 방어] Retry: 지수 백오프 (최대 3회)
  │
  └─ [미적용/추후 고려] Circuit Breaker

각 계층이 다른 문제를 해결한다.

세마포어는 동시 접근 폭탄을 막고, Rate Limiter는 API 할당량 초과를 막고, Timeout은 무한 대기를 막고, Retry는 일시적 실패를 복구하고, Circuit Breaker는 지속적 장애에서 서버를 보호한다.

이 중 현재 적용한 것과 아직 적용하지 않은 것이 있다. 중요한 건 각각이 왜 필요하고, 언제 도입해야 하는지를 이해하고 있는 것이다. 무조건 다 적용하는 게 아니라, 프로젝트 규모와 상황에 맞게 판단하는 거다.

다음 글에서는 스레드와 부하 테스트 이야기를 다룬다. 스레드 4개짜리 환경의 한계와, k6로 어떻게 검증했는지를 정리한다.

추리게임의 시나리오 생성 흐름은 이렇다. 풀스토리를 만들고, 용의자별 알리바이를 생성하고, 증거를 배치하고, 용의자 정보를 저장한다. 이 과정에서 LLM을 여러 번 호출하고, 각 결과를 DB에 저장한다.

처음에는 이 전체를 하나의 트랜잭션으로 묶었다. "전부 성공하거나 전부 실패하거나" 하는 게 안전하다고 생각했으니까. 근데 문제가 생겼다.

LLM 호출은 외부 API다. 응답이 올 때까지 기다려야 한다. 한 번 호출에 수 초씩 걸리는데, 이게 한 트랜잭션 안에서 여러 번 일어난다. 결과적으로 한 트랜잭션이 약 30초간 열려 있는 상황이 됐다.

DB 커넥션을 30초간 물고 있는 거다. 스레드가 4개인 환경에서 이러면 다른 요청이 커넥션을 못 얻어서 대기하게 된다. 커넥션 풀이 고갈되는 거다.

그전에, ACID부터 정리하자

트랜잭션을 쪼갠다는 건 ACID 중에서 Atomicity(원자성)를 포기하는 거다. 이 판단을 하려면 ACID가 뭘지 정확히 알고 있어야 했다.

Atomicity (원자성): 트랜잭션 안의 작업이 전부 성공하거나 전부 실패하거나. 중간 상태가 없다. 송금으로 치면 A 계좌에서 빼지고 B 계좌에 들어가는 게 하나로 묶여야 하는 거다.

Consistency (일관성): 트랜잭션 전후로 DB의 제약 조건이 항상 유지된다. FK, UNIQUE, NOT NULL 같은 제약이 깨지지 않는다.

Isolation (격리성): 동시에 실행되는 트랜잭션들이 서로 간섭하지 않는다. 내가 읽고 있는 데이터를 다른 트랜잭션이 바꿀 수 있는지 없는지, 이걸 어디까지 허용할지를 결정하는 게 Isolation Level이다.

Durability (지속성): 커밋된 트랜잭션은 시스템이 죽어도 사라지지 않는다. 디스크에 영구적으로 반영된다.

Isolation Level — 어디까지 격리할 것인가

동시성 문제를 다루다 보니 Isolation Level도 짚고 넘어가야 했다. 4단계가 있다.

READ UNCOMMITTED

다른 트랜잭션이 커밋하지 않은 데이터까지 읽을 수 있다. 이걸 더티 리드(Dirty Read)라고 한다. A가 데이터를 수정했는데 아직 커밋 전인데, B가 이 수정된 값을 읽어버리는 거다. A가 롤백하면 B가 읽은 데이터는 존재하지 않는 데이터가 된다. 실무에서는 거의 안 쓴다고 한다.

READ COMMITTED

커밋된 데이터만 읽을 수 있다. 더티 리드는 없다. 하지만 같은 트랜잭션 안에서 같은 쿼리를 두 번 날렸을 때 결과가 다를 수 있다. 이걸 Non-Repeatable Read라고 한다. 내가 읽는 사이에 다른 트랜잭션이 커밋해버리면 값이 바뀌는 거다. PostgreSQL의 기본값이다.

REPEATABLE READ

같은 트랜잭션 내에서 같은 쿼리는 항상 같은 결과를 반환한다. 트랜잭션 시작 시점의 스냅샷을 기준으로 읽는다. 다만 팬텀 리드(Phantom Read)가 발생할 수 있다. 다른 트랜잭션이 새 행을 INSERT하면 다음 쿼리에서 갑자기 새 행이 보이는 것이다. (MySQL InnoDB는 갤 락으로 이것도 막지만, 표준 SQL 정의상으로는 발생할 수 있다.) MySQL InnoDB의 기본값이다.

SERIALIZABLE

완전한 직렬화. 모든 트랜잭션이 순서대로 실행되는 것처럼 보장한다. 가장 안전하지만 성능이 가장 떨어진다. 동시성이 거의 없어지니까.

트랜잭션을 어떻게 쪼갰는가

30초짜리 트랜잭션의 근본 원인은 트랜잭션 안에서 외부 API(LLM)를 호출하고 있었다는 것이다. 트랜잭션이 열려 있는 동안 DB 커넥션을 계속 물고 있고, LLM 응답을 기다리는 수 초 동안 그 커넥션은 다른 요청이 쓸 수 없다.

해결책의 핵심은 간단했다. LLM 호출은 트랜잭션 밖으로 빼고, DB 저장만 트랜잭션으로 묶는다.

근데 모든 데이터를 같은 방식으로 처리할 수는 없었다. 데이터마다 중요도가 다르니까.

용의자 심문 — 휘발성 데이터

용의자 심문은 플레이어가 용의자에게 질문을 던지고, LLM이 응답을 생성하는 구조다. 이 데이터는 게임이 실패하거나 성공하자마자 삭제한다. DB 부하를 줄이기 위해 일부러 그렇게 설계했다.

이 경우에는 품질과 빠른 응답이 데이터 보존보다 중요하다고 판단했다.

그래서 LLM 호출은 트랜잭션 완전히 밖에서 처리했다. 응답을 받은 후 DB에 저장하는 부분만 짧은 트랜잭션으로 묶었다. LLM 호출 성공 → DB 저장 실패하면? 어차피 삭제될 데이터니까 크게 문제되지 않는다. 플레이어에게 에러 메시지를 보여주고 다시 시도하게 하면 된다.

[트랜잭션 없음] LLM 호출 → 응답 수신
[트랜잭션 시작] DB 저장
[트랜잭션 끝] 
→ 커넥션 점유: 수백ms 이내

시나리오 생성 — 절대 잃으면 안 되는 데이터

시나리오 생성은 완전히 다른 문제였다.

그리고 이 데이터는 생성 비용이 크다. LLM을 여러 번 호출해야 하고, 각 호출마다 validation을 거친다. 트랜잭션이 실패해서 전체를 다시 만들어야 하면 비용이 엄청나다.

풀스토리, 알리바이, 증거, 용의자 정보 — 이것들은 서로 연관관계가 있고, 추리게임 특성상 논리적 정합성이 중요하다. 알리바이가 풀스토리와 안 맞으면 게임 자체가 말이 안 된다. 플레이어를 납득시켜야 하니까.

[트랜잭션 1] 풀스토리 생성 + 저장
[트랜잭션 2] 알리바이 생성 + 저장
[트랜잭션 3] 증거 생성 + 저장
[트랜잭션 4] 용의자 정보 생성 + 저장

그래서 노드 단위로 트랜잭션을 분리했다.

각 노드에서 LLM 호출은 트랜잭션 밖에서 하고, 결과를 DB에 저장하는 것만 트랜잭션으로 묶었다. 이렇게 하면:

하나, 트랜잭션 3(증거)에서 실패해도 트랜잭션 1(풀스토리)과 2(알리바이)는 이미 저장되어 있다.

둘, 실패한 노드만 재시도하면 된다. 전체를 처음부터 다시 할 필요가 없다.

셋, 각 트랜잭션의 커넥션 점유 시간이 극적으로 줄어든다.

단점도 있다. 풀스토리는 저장되었는데 알리바이 생성에 실패하면, 풀스토리만 덩그러니 있는 불완전한 상태가 된다. Atomicity를 포기한 것이다. 이걸 감수한 이유는, 불완전한 상태여도 실패한 노드부터 재시도하면 복구가 가능하기 때문이다. 전체를 날리는 것보다 훨씬 낫다.

이건 Saga 패턴의 기본 아이디어에서 차용했다. Saga는 긴 트랜잭션을 여러 개의 로컬 트랜잭션으로 나누고, 실패 시 보상 트랜잭션(compensation)을 실행해서 일관성을 맞춘다. 내 경우에는 보상 트랜잭션 대신 "실패한 노드부터 재시도"라는 더 단순한 전략을 썼다.

결과

트랜잭션 분리 후:

커넥션 점유 시간: 30초 → 2~3초

LLM 호출 대기 시간이 트랜잭션 밖으로 빠졌으니 당연한 결과다. 각 트랜잭션은 순수하게 DB 쓰기만 하니까 2~3초면 충분했다.

커넥션 풀 — 이 문제와 직결되는 것

내가 30초짜리 트랜잭션을 돌리고 있었을 때, 스레드 4개가 각각 커넥션을 물고 30초씩 점유하고 있었다면, 커넥션 풀이 고갈되는 거다. 새로운 요청이 들어와도 커넥션을 못 얻어서 타임아웃이 난다.

트랜잭션을 쪼개면서 커넥션 풀에 대해서도 고민하게 됐다.

커넥션 풀은 DB 커넥션을 미리 여러 개 만들어두고, 요청이 올 때마다 하나씩 빌려주는 구조다. Spring Boot를 쓰면 기본적으로 HikariCP가 커넥션 풀을 관리한다.

HikariCP의 기본 maximumPoolSize는 10이다. 스레드가 4개라 트랜잭션이 4개 동시에 돌 수 있고, 각각 30초씨 점유하면 4개의 커넥션이 30초간 묶인다. 나머지 6개도 다른 단순 쿼리들이 썼야 하는데, 그마저도 부족해질 수 있다.

트랜잭션을 쪼갰더니 이 문제가 자연스럽게 해결됐다. 커넥션 점유가 2~3초로 줄었으니까.

N+1 문제 — 추리게임과 연관관계

N+1이란, 1번의 쿼리로 시나리오를 가져온 후, 각 시나리오의 용의자를 가져오기 위해 N번의 추가 쿼리가 나가는 것이다.

SELECT * FROM scenario;                    -- 1회
SELECT * FROM suspect WHERE scenario_id = 1; -- N회 (시나리오 수만큼)
SELECT * FROM suspect WHERE scenario_id = 2;
SELECT * FROM suspect WHERE scenario_id = 3;
...

해결 방법은 크게 두 가지다:

Fetch Join: 한 번의 쿼리로 연관된 엔티티까지 한번에 가져온다.

SELECT s FROM Scenario s JOIN FETCH s.suspects

Batch Size: 지연 로딩 시 IN 절로 모아서 쿼리한다.

spring.jpa.properties.hibernate.default_batch_fetch_size: 100

이러면 N번 대신 1~2번의 쿼리로 처리할 수 있다.

인덱스와 B+Tree

쿼리 성능을 신경 쓰다 보면 인덱스도 짚고 넘어가야 한다.

DB 인덱스는 대부분 B+Tree 구조다. B+Tree를 이해하면 왜 인덱스가 빠른지, 언제 있어야 하는지를 설명할 수 있다.

B+Tree의 핵심 특징:

하나, 리프 노드에만 데이터가 있다. 내부 노드는 키만 갖고 있고, 실제 데이터는 리프 노드에 저장된다.

둘, 리프 노드가 링크드 리스트로 연결되어 있다. 범위 검색(WHERE price BETWEEN 100 AND 500) 시 순차적으로 따라가면 되니까 빠르다.

셋, 트리 높이가 낮다. 대량의 데이터가 있어도 3~4단계면 원하는 데이터에 도달한다. 이게 곧 디스크 I/O를 줄이는 핵심이다.

인덱스가 있으면 좋은 경우: WHERE 절에 자주 쓰이는 컨디션, JOIN 컨디션, ORDER BY 절.

인덱스가 오히려 느려지는 경우: INSERT/UPDATE/DELETE가 빈번한 테이블. 인덱스도 같이 업데이트해야 하니까 쓰기 성능이 떨어진다.

내 프로젝트에서는 시나리오 조회가 잦고, 용의자/단서는 scenario_id로 조회하는 경우가 많으니까 이 컨디션에 인덱스가 필요한 구조다.

정리

이번 글의 핵심은 "트랜잭션을 쪼갬으로써 얻는 것과 잃는 것"을 정확히 인식하고 판단했다는 것이다.

얻는 것: 커넥션 점유 시간 단축, 커넥션 풀 고갈 방지, 부분 재시도 가능.

잃는 것: Atomicity. 중간에 실패하면 불완전한 상태가 될 수 있다.

이 트레이드오프를 이해하고, 데이터 중요도에 따라 다른 전략을 적용한 게 이번 경험의 핵심이다.

다음 글에서는 LLM이라는 외부 API를 호출하면서 발생하는 다른 문제들 — 타임아웃, 재시도, 장애 차단 — 을 다룬다.

앞에서 세마포어로 동시 접근 수를 4개로 제한했다. 그런데 이것만으로는 부족했다.

세마포어는 "동시에 몇 개까지 허용할 것인가"를 제어하지, "얼마나 빠르게 호출할 것인가"는 제어하지 않는다. 예를 들어 permit 4개가 전부 비어있는 상태에서 요청 4개가 동시에 들어오면, 4개가 순간적으로 한꺼번에 API를 때린다. 프리티어 RPM이 4인 상황에서 이렇게 되면 한 번에 할당량을 다 써버린다.

그래서 호출 속도 자체를 제어할 수단이 필요했고, Guava의 RateLimiter를 도입했다.

토큰 버킷 vs 리키 버킷

Rate Limiting 알고리즘을 찾아보면 크게 두 가지가 나온다. 토큰 버킷(Token Bucket)과 리키 버킷(Leaky Bucket)이다. 둘 다 "속도를 제한한다"는 목적은 같은데, 동작 방식이 다르다.

토큰 버킷 (Token Bucket)

일정 속도로 토큰이 버킷에 채워진다. 요청이 들어오면 토큰을 1개 소비한다. 토큰이 없으면 대기하거나 거부한다.

[토큰 버킷: ●●●●]  ← 일정 속도로 토큰 추가
요청 들어옴 → 토큰 1개 소비 → [●●●]
요청 들어옴 → 토큰 1개 소비 → [●●]
...
토큰 0개 → 대기

핵심 특징은 버스트(burst)를 허용한다는 것이다. 토큰이 쌓여 있으면 한꺼범에 여러 개를 소비할 수 있다. 예를 들어 한동안 요청이 없어서 토큰이 4개 쌓여 있으면, 순간적으로 4개를 연속 처리할 수 있다.

리키 버킷 (Leaky Bucket)

요청이 버킷에 들어가고, 버킷의 밑바닥에 난 구멍으로 일정한 속도로 빠져나간다. 버킷이 가득 차면 새 요청은 버려진다.

요청 → [버킷에 쌓임] → 일정한 속도로 처리
                          ↑ 항상 같은 속도

핵심 특징은 출력 속도가 항상 일정하다는 것이다. 버스트가 없다. 아무리 요청이 몰려도 처리 속도는 변하지 않는다.

차이 정리

Guava RateLimiter는 토큰 버킷이다

Guava의 RateLimiter는 토큰 버킷 기반이다. 내 프로젝트에서는 이렇게 썼다:

RateLimiter rateLimiter = RateLimiter.create(4.0 / 60); // 분당 4회 = 초당 약 0.067회

acquire()를 호출하면, 토큰이 있으면 즉시 통과하고, 없으면 다음 토큰이 생길 때까지 Thread.sleep()으로 대기한다. 거부가 아니라 대기다. 이 점이 중요했다. 요청을 버리는 게 아니라 순서를 기다리게 하는 거니까, 게임 플레이어 입장에서는 "느리지만 결국 된다"는 경험을 줄 수 있었다.

SmoothBursty vs SmoothWarmingUp

Guava RateLimiter에는 두 가지 모드가 있다. 이것도 찾아보고 고민했다.

SmoothBursty (RateLimiter.create(rate))

기본값이다. 미리 쌓인 토큰을 한번에 쓸 수 있다. 예를 들어 10초간 요청이 없었으면, 그동안 토큰이 쌓여서 다음 요청들은 버스트로 처리될 수 있다.

SmoothWarmingUp (RateLimiter.create(rate, warmupPeriod, unit))

콜드 스타트 후 점진적으로 속도를 올린다. 오랫동안 요청이 없다가 갑자기 몰리면, 처음에는 느리게 처리하다가 warmupPeriod동안 점점 속도를 높인다. DB 커넥션이나 외부 서비스가 워밍업이 필요한 경우에 적합하다.

내가 내린 판단

SmoothBursty를 선택했다.

추리게임 특성상 요청이 계속 들어오는 게 아니라 플레이어가 조사하고, 심문하고, 단서를 확인하는 사이사이에 간격이 있다. 그 간격동안 토큰이 쌓이고, 다음 액션 때 버스트로 처리할 수 있는 게 더 자연스러웠다. WarmingUp은 우리 서비스에 필요한 시나리오가 아니었다. 워밍업이 필요한 외부 의존성이 없었으니까.

세마포어와 Rate Limiter의 역할 차이

이 둘을 같이 거는 이유를 정확히 정리해두고 싶었다.

세마포어: 동시 접근 수를 제한한다. "4개 이상 동시에 들어오지 마라."

Rate Limiter: 호출 속도를 제한한다. "1분에 4회 이상 호출하지 마라."

세마포어만 있으면? permit 4개가 동시에 소비되면서 API를 순간적으로 4번 때릴 수 있다. RPM 초과다.

Rate Limiter만 있으면? 속도는 제어되지만, 대기 스레드가 무한정 쌓일 수 있다. 스레드 4개짜리 환경에서 전부 대기 상태에 빠지면 다른 요청을 아예 처리 못한다.

그래서 둘 다 걸었다. 세마포어가 동시 접근을 물리적으로 차단하고, Rate Limiter가 통과한 요청의 속도를 한번 더 조절하는 구조다.

요청 → [Semaphore: 동시 4개까지만 통과] → [RateLimiter: 분당 4회 속도로 조절] → LLM API 호출

그럼 분산 환경에서는 어떻게 하나

이건 직접 적용하지는 않았지만, 고민한 부분이다.

처음에는 Redis로 Rate Limiting을 하려고 했다. Redis는 중앙 집중형이라 여러 서버가 있어도 하나의 Rate Limit를 공유할 수 있다. 일반적으로 두 가지 방식이 있다:

고정 윈도우 (Fixed Window)

INCR api_calls:{current_minute}
EXPIRE api_calls:{current_minute} 60

현재 분(또는 초)를 키로 잡고, 해당 시간대의 호출 수를 카운트한다. 간단하지만 윈도우 경계에서 문제가 생긴다. 예를 들어 0:59에 4회, 1:00에 4회 호출하면 실질적으로 2초 사이에 8회 호출이 되는 것이다.

슬라이딩 윈도우 (Sliding Window)

Redis의 Sorted Set을 사용한다. 각 요청의 타임스탬프를 score로 넣고, 현재 시점에서 1분 이내의 요청 수를 카운트한다.

ZADD api_calls {timestamp} {request_id}
ZREMRANGEBYSCORE api_calls 0 {timestamp - 60}
ZCARD api_calls

고정 윈도우의 경계 문제가 없다. 더 정확하다. 다만 메모리 사용량이 더 많다.

그런데 나는 Redis를 안 썼다

고민을 했지만 안 썼다. 이유는 간단했다.

내 프로젝트는 단일 JVM 위에서 돌아가는 단일 서버다. 서버가 여러 대가 아니다. Redis는 본질적으로 여러 서버가 하나의 Rate Limit를 공유해야 할 때 필요한 것이다. 단일 서버에서 Redis를 도입하면:

하나, 네트워크 홀이 추가된다. Redis 서버와의 통신 지연이 생긴다.

둘, 운영 복잡도가 올라간다. Redis 서버를 따로 띄워야 하고, 장애 포인트가 하나 늘어난다.

셋, 얻는 게 없다. 단일 서버니까 분산 Rate Limiting의 이점인 "여러 서버 간 일관된 제한"이 필요 없다.

Guava RateLimiter는 단일 프로세스 내에서 동작하고, 외부 의존성이 없고, 설정이 간단하다. 현재 규모에서는 이것으로 충분했다.

물론 나중에 서버를 스케일 아웃해서 여러 대로 늘리게 된다면, 그때는 Redis 기반으로 전환해야 한다. 그때 가서 슬라이딩 윈도우를 쓰든, 고정 윈도우를 쓰든 그건 그때 판단할 문제다. 현재 단계에서는 Guava가 정답이었다.

결과

세마포어 + Guava Rate Limiter 이중 방어를 적용한 결과:

429 에러(RPM 초과) 발생률: 80% → 10% 이내

10%가 완전히 0이 아닌 이유는, 게임 특성상 한 세션에서 여러 번의 LLM 호출이 연속으로 일어나는 구간이 있기 때문이다. 완전히 없애려면 RPM 자체를 늘려야 하는데, 프리티어라 그건 내 손에 없는 문제다. 10% 이내라면 충분히 수용 가능한 수준이라고 판단했다.

다음 글에서는 트랜잭션을 어떻게 쪼갰는지, 그리고 왜 쪼갤 수밖에 없었는지를 정리한다.

프리티어 LLM API를 쓰고 있었다. 당연히 동시 호출 수에 제한이 있었고, 백엔드 스레드도 4개로 제한된 환경이었다. 동시에 4개 이상의 요청이 LLM API를 때리지 못하게 제어할 수단이 필요했다.

처음부터 세마포어를 쓰려고 했던 건 아니다. synchronized도 생각했고, ReentrantLock도 봤다. 근데 결국 "동시에 몇 개까지 허용할 것인가"라는 요구사항에서 답이 갈렸다. 여기서부터 정리한다.

synchronized vs ReentrantLock vs Semaphore

이 세 가지를 비교하면서 고민했던 과정이다.

synchronized

Java에서 가장 기본적인 동기화 수단이다. 모니터 락 기반으로 동작하고, 한 번에 하나의 스레드만 임계 영역에 들어갈 수 있다.

synchronized (lock) {
    // 한 번에 1개 스레드만 진입
    callLLMApi();
}

간단하고 실수가 적다. 블록을 벗어나면 자동으로 락이 풀리니까 unlock을 깜빡할 일이 없다. 근데 치명적인 제한이 있다. permit이 항상 1이다. 즉 mutex다. 내 상황처럼 동시에 4개까지 허용해야 하면 쓸 수가 없다.

ReentrantLock

synchronized의 확장판이라고 보면 된다. 명시적으로 lock()과 unlock()을 호출해야 하고, 그만큼 유연하다.

ReentrantLock lock = new ReentrantLock();
lock.lock();
try {
    callLLMApi();
} finally {
    lock.unlock();
}

synchronized와 다른 점은 tryLock(타임아웃 지정 가능), lockInterruptibly(인터럽트 가능), 그리고 공정성(fairness) 설정이 가능하다는 것이다. 근데 이것도 본질적으로는 mutex다. 동시에 1개만 들어갈 수 있다. 내 상황에선 역시 부적합했다.

Semaphore

세마포어는 permit(허가증) 개수를 지정할 수 있다. 동시에 N개의 스레드가 진입할 수 있다는 점에서 위 두 가지와 근본적으로 다르다.

Semaphore semaphore = new Semaphore(4); // 동시에 4개 허용
semaphore.acquire(); // permit 1개 소비
try {
    callLLMApi();
} finally {
    semaphore.release(); // permit 반환
}

정리하면 이렇다:

결론은 단순했다. 동시에 4개까지 허용해야 했다. synchronized나 ReentrantLock은 permit이 1이라 안 됐고, permit을 N으로 잡을 수 있는 건 세마포어뿐이었다. 만약 permit이 1이었으면 그냥 ReentrantLock을 썼을 거다.

그래서 세마포어가 내부적으로 어떻게 도는 건가: AQS

세마포어를 쓰기로 한 이후에 궁금해진 게 있었다. acquire()를 호출하면 내부에서 뭐가 일어나는 거지? 그래서 파봤다.

Java의 Semaphore, ReentrantLock, CountDownLatch 같은 것들은 전부 AQS(AbstractQueuedSynchronizer)라는 프레임워크 위에 구현되어 있다. AQS의 핵심은 두 가지다.

1. state 변수

AQS는 int state라는 변수 하나로 동기화 상태를 관리한다.

세마포어에서는 state가 곧 남은 permit 수다. acquire()를 호출하면 state를 1 감소시키려고 시도하고, state가 0이면 더 이상 permit이 없으니까 스레드는 대기한다. release()를 호출하면 state를 1 증가시키고 대기 중인 스레드를 깨운다.

참고로 ReentrantLock에서는 state가 락 획득 횟수(재진입 카운트)다. 같은 AQS인데 state의 의미가 달라지는 게 재밌다.

2. CLH 큐

permit을 얻지 못한 스레드는 CLH(Craig, Landin, Hagersten) 큐라는 대기열에 들어간다. 링크드 리스트 형태로, 각 노드가 이전 노드의 상태를 관찰하면서 자기 차례를 기다린다. permit이 반환되면 큐의 앞쪽 스레드부터 깨워서 진입시킨다.

[Thread-A: 실행중] → [Thread-B: 대기] → [Thread-C: 대기]
                     ↑ CLH 큐

스레드가 대기할 때는 LockSupport.park()로 OS 레벨에서 블로킹되고, 깨울 때는 LockSupport.unpark()를 사용한다. 바쁜 대기(busy waiting)가 아니라 실제로 CPU를 양보하는 구조다. 이 부분이 중요한 게, 만약 busy waiting이었으면 스레드 4개짜리 환경에서 CPU를 다 잡아먹어버렸을 거다.

CAS(Compare-And-Swap) 연산

AQS에서 state 변수를 변경할 때 일반적인 대입문을 쓰지 않는다. CAS 연산을 쓴다. CPU 레벨에서 제공하는 원자적(atomic) 연산이다.

동작 방식은 이렇다:

CAS(메모리 주소, 예상값, 새 값)
→ 메모리의 현재 값이 예상값과 같으면 → 새 값으로 교체 (성공)
→ 다르면 → 아무것도 안 함 (실패)

예를 들어 세마포어의 state가 현재 3이고, 스레드 A가 acquire()를 호출하면:

CAS(state, 3, 2)  // "state가 3이면 2로 바꿔라"
→ 성공하면 permit 획득
→ 실패하면 (다른 스레드가 먼저 바꿨으면) 재시도

핵심은 락 없이 원자적으로 값을 변경할 수 있다는 것이다. Java의 AtomicInteger, AtomicReference, AtomicLong 같은 것들이 전부 CAS 기반이다. 세마포어도, ReentrantLock도 내부적으로 이 CAS를 써서 state를 변경한다.

CAS의 한계: ABA 문제

값이 A → B → A로 변경된 경우, CAS는 "원래 A였고 지금도 A니까 변경 안 됐구나"라고 판단해버린다. 실제로는 변경되었는데 감지하지 못하는 것이다. Java에서는 AtomicStampedReference로 버전 번호를 함께 관리해서 이 문제를 해결할 수 있다. 내 프로젝트에서 이게 문제가 되진 않았지만, 이런 한계가 있다는 건 알고 있어야 한다고 생각했다.

Fair vs Unfair 세마포어

new Semaphore(4);          // unfair (기본값)
new Semaphore(4, true);    // fair

이것도 고민을 했다.

Unfair (기본값)

새로 도착한 스레드가 CLH 큐에 있는 스레드보다 먼저 permit을 뺏을 수 있다. 큐를 건너뛰는 거다.

장점은 처리량(throughput)이 높다는 것이다. 큐에서 스레드를 깨우려면 컨텍스트 스위칭이 필요한데, 이미 실행 중인 스레드가 바로 진입하면 이 비용을 아낄 수 있다.

단점은 기아(starvation) 문제다. 운이 나쁜 스레드는 큐에서 계속 밀려날 수 있다.

Fair

반드시 CLH 큐 순서대로 permit을 부여한다. FIFO가 보장되니까 기아 문제가 없다.

단점은 매번 큐를 확인하고 컨텍스트 스위칭을 해야 해서 처리량이 떨어진다.

내가 내린 판단

RPM이 4인 환경이다. 동시 요청 자체가 극히 적다. 이 상황에서 fair/unfair 차이는 체감되지 않는다. 기아 문제가 발생하려면 경쟁이 치열해야 하는데, 애초에 경쟁할 스레드가 별로 없다. 그래서 기본값(unfair)을 유지했다. 불필요한 컨텍스트 스위칭 비용을 굳이 감수할 이유가 없었다.

트래픽이 늘어나서 동시 요청이 수십~수백 단위가 된다면 그때는 fair를 고려해야 할 수도 있다. 하지만 현재 규모에서는 오버엔지니어링이라고 판단했다.

최종 구조

요청 → [Semaphore.acquire()] → [Rate Limiter 대기] → LLM API 호출 → [Semaphore.release()]
         ↑ 동시 4개 제한           ↑ 초당 호출 속도 제한

세마포어는 동시 접근 수를 제한하고, Rate Limiter는 호출 속도를 제한한다. 역할이 다르다.

세마포어만 있으면 4개가 동시에 순간적으로 몰릴 수 있다. Rate Limiter만 있으면 속도는 제어되지만 대기 스레드가 무한정 쌓일 수 있다. 그래서 둘 다 걸었다. 이 이중 방어에 대해서는 다음 글(Rate Limiting 편)에서 더 자세히 다룬다.

사실 시험준비할 시간이 너무 없어서(과제와 시험의 연속..) 붙을 생각안하고 그냥 sql 공부나 좀 해놔야지 하는 마음으로 깔짝거려 본거같은데 붙어버림 ... 예상 한 30점대였는데 합격했대서 놀라따.

시험후기

SQLD 노랭이 책 개쓸모없다. 똑같은 문제 2개정도 본거같긴한데 신유형이 많았고 더러운 문제가많았다. 오히려 민트책?유선배? 그책 예상기출에 비슷한 유형이 많았던듯 (내돈내산..) 이 책 풀면서 아 문제가 왜이리 조잡해 ㅋ 했는데 그 조잡한 유형이 많이 나옴

시험 공부하면서 조인 헷갈리던게 좀 잡히는 느낌이 들었다 물론 프로젝트에서 쓰려면 한참 더 공부해야겠지만 기초를 다지는데 조금은 도움이 된거같다☺️

풀이과정 및 리뷰

• 문제 접근:

  • 학교(S)를 기준으로 좌표가 왼쪽(plus), 오른쪽(minus) 으로 나뉘므로 각각 별도 관리

  • 버스는 한 번에 K명까지 태울 수 있으므로, 멀리 있는 아파트 단지부터 학생을 수송하는 것이 최적

  • 학생 수가 버스 정원을 넘으면 여러 번 왕복해야 하고,

    남은 인원이 있으면 가까운 단지 학생들과 합쳐서 태우기 가능 → 그 단지는 별도의 왕복 비용이 발생하지 않음

• 시간복잡도: $O(N log N)$

• 풀이과정

  • 단지 정보를 dist(학교와의 거리) 기준 내림차순 정렬(이때 Plus, Minus 2개 리스트 생성해 별도관리)
  • cnt 변수를 이용해 아직 등교시키지 못한 학생 수 누적
  • 각 단지를 돌면서 cnt에 해당 단지 학생 수를 더하고, cnt > 0인 동안 버스 정원 K만큼 빼면서 왕복 거리를 추가

• 개선점

  정렬 comparator

    Collections.sort(list, (a,b) -> b.dist - a.dist);

  로 람다식 사용하면 더 직관적

  메모리 절약

  plus, minus 나눠서 저장하지 않고, 입력 시 좌표 비교 후 바로 두 리스트에 add하면 충분

풀이과정 및 리뷰

• 문제 접근: H왕국을 제외하고, 연결요소 수를 max순으로 정렬한 후 C왕국 연결 수 + max연결 수 * T번 반복하면 되겠다.

• 시간복잡도: $O(N + M + N log N)$

• 풀이과정

  1. 그래프 구성
     • 무방향 그래프를 인접 리스트로 구성
  2. 두 개의 BFS 수행
     • C에서 한 번 BFS → start 변수로 연결 요소 크기 저장
     • H에서도 BFS 수행 (visited로 방문 체크하므로, C와 H및 앞으로 탐색하는 연결요소들은 visited로 모두 방문체크해 재방문하지 않)
  3. 방문하지 않은 노드들로 BFS 수행
     • 각각의 연결 요소 크기를 리스트에 저장
  4. 리스트 정렬 후 T개만 선택
     • 연결 요소 중 큰 것부터 T개만 선택하여 크기 합산
  5. 정답 출력
     • start + 상위 T개의 연결 요소 크기 합

• 개선점

  1. ❗ list.get(i)에서 예외 가능성 있음

    for(int i = 0; i < T; i++) {
        res += list.get(i);
    }

  • list.size() < T인 경우 IndexOutOfBoundsException 발생 가능

  • → 안전하게 고치는 방법:

    for(int i = 0; i < Math.min(T, list.size()); i++) {
      res += list.get(i);
    }

    2. 🔧 코드 스타일 개선

  • graph = new ArrayList[N+1]; 보다는 graph = new ArrayList[N + 1];로 띄어쓰기 일관성 유지 ( 진짜 별결다 트집)

  • Collections.sort(..., Collections.reverseOrder()) → 람다로 더 간결하게 쓸 수도 있음:

bfs VS dfs?

✅ DFS vs BFS 선택 기준 (이 문제에서)

💡 이 문제에서는?

✅ BFS 추천

이유:

1. 입력 노드 수가 최대 수만 단위 → 스택 오버플로우 위험은 낮지만 무시할 수 없음
2. BFS는 재귀 없이 구현 가능 → Java에서는 안정적
3. 너비 우선이기 때문에 모든 노드에 대해 동일한 방식으로 탐색 가능 (특히 연결 요소 분리 시 좋음)
4. 코드 구조가 복잡하지 않고 직관적 (지금처럼 큐 기반으로)

📌 결론

BFS가 이 문제에서는 더 적절한 선택입니다.

• DFS도 기능적으로 가능하지만, Java에서는 BFS가 안정성과 가독성 면에서 유리
• 현재 코드도 BFS로 잘 짜여 있어서 유지하는 게 좋습니다.

풀이과정 및 리뷰

• 문제 접근: bfs사용해 R / G / B마다 탐색하되, 인자로 isGreen을 받아 적록색약인 사람과 아닌사람의 영역을 구분하려고 함
• 시간복잡도: $O(N^2)$
• 풀이과정
  • 입력받은 보드에서 BFS를 이용해 일반인의 시각으로 색상 영역 개수를 셈
  • visited 배열 초기화 후, 적록색약자는 R과 G를 같은 색으로 간주하며 다시 BFS 수행
  • 두 경우의 영역 수를 각각 출력하여 구분된 영역 개수 비교
• 개선점
  • 조건 중복 발생. 아래처럼 같은 색인지 판단하는 함수를 분리하는 것이 가독성 및 재사용성에 좋음:

if(board[nr][nc] == board[i][j]) {
    ...
}
if(isGreen) {
    if(board[i][j] == 'R' && board[nr][nc] == 'G' || board[i][j] == 'G' && board[nr][nc] == 'R') {
        ...
    }
}

static boolean isSameColor(char a, char b, boolean isGreen) {
    if (a == b) return true;
    if (isGreen && ((a == 'R' && b == 'G') || (a == 'G' && b == 'R'))) return true;
    return false;
}

if (isSameColor(board[i][j], board[nr][nc], isGreen)) {
    visited[nr][nc] = true;
    q.offer(new int[]{nr, nc});
}

풀이과정 및 리뷰

• 문제 접근: 오름차순으로 정렬되어 입력되므로 입력값을 [i+1] - [i]로 빼서 둘 사이의 차이를 구해 배열에 저장한 후 이를 사용해서 최소값을 구한다.

  → “가장 큰 차이 (K-1개)를 제외한 나머지를 모두 더하면 최소합이 된다”

• 시간복잡도: $O(N log N)$

  • 인접 차이 계산: O(N)
  • 정렬: O(N log N)
  • 합 계산: O(N)

• 풀이과정

  • 테스트 케이스 5 3 / 1 3 5 6 10 을 각각의 자릿수 차이만큼 배열로 저장 [2,2,1,4]
  • 이후 해당 배열 height 을 정렬한 후 , 0 ~ N - K - 1 만큼 순회하며 sum에 누적합 저장

• 개선점

  정렬 없이 힙(우선순위 큐) 사용 고려

  • Arrays.sort() 대신 우선순위 큐(PriorityQueue) 사용 시, 가장 작은 N-K개의 합만 필요한 경우 성능 최적화 가능 (특히 큰 입력일 때).

    예:

    PriorityQueue<Integer> pq = new PriorityQueue<>();
    // add all diffs
    for (...) pq.add(diff[i]);
    // sum the N - K smallest
    for (int i = 0; i < N - K; i++) sum += pq.poll();

    하지만 이 문제는 N <= 10^5 수준이면 정렬이 더 간단하고 충분히 빠릅니다.

풀이과정 및 리뷰

• 문제 접근:

  • 토마토는 익은 토마토들(1)이 동시에 bfs탐색해야되므로, bfs를 쓸때 1인 것들을 모두 찾아 동시에 큐에 집어넣고 탐색이 끝나면 cnt++, 다음 1인 노드들 탐색하는 식으로 풀어야겠다고 생각함
  • bfs탐색이 끝난후에는 tomato배열을 탐색해 0을 마주치는 순간 바로 -1을 리턴하도록 함

• 시간복잡도: $O(Z * M * N)$

• 풀이과정

  • tomato / visited 3차원 배열 생성 및 델타(2차원배열로 3차원 표현) 선언

  • tomato 배열을 채우면서 입력값이 1이라면 따로 리스트에 i/j/k 저장

    → if(a == 1) list.add(new int[]{k, i, j});

  • 리스트를 인자로 받는 bfs메서드 선언

    • 큐 두개 생성

      • 바깥 큐 : 익은 토마토(1)을 동시에 순회하기 위한 큐

        → Queue<List<int[]>> all = new ArrayDeque<>();

      • 안쪽 큐 : 익은 토마토 리스트들을 각각 순회하며 인접 4방향 탐색

        • 이때, 방문하지않았고/인접노드값이 0이라면 1로 바꾸고 list에 넣음

          → List<int[]> put = new ArrayList<>(); : 익은 토마토들의 인접 4방향 탐색해서 익힌 토마토들의 위치값들로, 익은 토마토들의 4방향 탐색이 끝나면(= 안쪽 큐가 비면)한꺼번에 바깥큐에 집어넣음

          이때, 리스트가 빈다면 더이상 바깥큐에 집어넣지않아서 큐를 비게 만든다.

          → List<int[]> after = all.poll(); : 바깥큐에 집어넣은 익은 토마토들을 받음

            → 안쪽 큐를 순회하며 안쪽 큐가 빌경우 cnt++함( = 하루지남)

    - 모든 반복문이 종료된 후, tomato배열 전체를 탐색하며 0인값이 존재한다면 익지 않은 토마토가 존재하는 것이므로 -1 리턴하면서 종료, 그게 아니라면 날짜(cnt) 리턴하면서 종료

• 개선점

  • BFS에서 visited 처리 위치

    if(!visited[nr][nc][nz] && tomato[nr][nc][nz]==0){
      visited[nr][nc][nz] = true;
      tomato[nr][nc][nz] = 1;
      put.add(new int[]{nr,nc,nz});
    }

    벽(-1)이나 이미 익은 토마토(1)에 대해 visited가 먼저 체크됨 → 논리적으로 안전하지만, 배열 순서 꼬이면 BFS가 정상 작동 안 함

    → tomato==0 조건 안쪽에서 visited 체크 → 불필요한 visited 체크 방지

  • BFS 구조 개선 가능

    • 지금 BFS 구조: Queue<List<int[]>> all + 내부에서 또 Queue<int[]> q → 중첩 큐 구조

    • 개선: 단일 Queue<int[]> + level 크기만큼 for문 처리로 단순화 가능

      Queue<int[]> q = new ArrayDeque<>();
      int days = 0;
      
      while(!q.isEmpty()){
        int size = q.size();
        for(int s=0; s<size; s++){
            int[] cur = q.poll();
            // 6방향 전파
        }
        days++;
      }

  • cnt 처리 방식

    • 현재: cnt++ → BFS 반복마다 증가
    • 개선: level 단위 BFS에서 마지막 단계에서 증가하지 않도록 조정 → 실제 걸린 날짜 정확히 계산

  • 배열 순서 관련 개선

    • [Z][M][N] → 높이, 행, 열 순서로 통일하면 입력과 BFS, 델타 적용이 직관적

      → 즉, 3차원 배열은 일반적으로 높이 / 행 / 열 순으로 작성함

  • 주요 개선점 : 복합 큐 쓸 필요가 없음. 단일 큐로 구현 가능

현재 진행중인 상황과 앞으로의 계획

현재

• 1일 2알고리즘 알고리즘 종류 선택해 1문제 풀기(dp/그리디/bfs&dfs/재귀/자료구조 등) 알고리즘 구분짓지 않고 랜덤 1문제 풀기

약한 부분 -> dp,그리디,재귀 ...

목표

• 웬만한 알고리즘에 익숙해졌다 싶으면 프로그래머스로 넘어가기(다익스트라 등 심화개념포함)

처음 코딩테스트 준비를 할때 백준과 프로그래머스 중 어디서 시작해야할지 막막했는데, 이제와서 생각해본다면 백준으로 알고리즘 유형을 익히고 프로그래머스로 넘어가는게 제일 좋은 방법인것같다.

백준

• 장점
  • 유형별로 잘 나뉘어져 있음
  • 한가지 유형만 집중해서 풀기 좋음
• 단점
  • 다른 사람들의 코드를 참고하기가 조금 귀찮음(구글링해야함)
    • 한가지 알고리즘 유형에만 집중하면 돼서 다각적인 사고력 기르기에는 조금 부족한거같다(아직 골드까지만 풀어서 그런걸지도..)

프로그래머스

• 장점
  • 문제 풀이 직후 다른 사람들의 씽크빅 코드 참고가능
  • 다방면으로 사고력을 기를 수 있는 질 좋은 문제가 많음. 스킬 늘리기 좋을 듯
  • 듣기론 실제 기업코테와 응시환경이 유사함
• 단점
  • 첫 시작을 프로그래머스로 한다면, 아직 문법조차 익숙하지 않은 단계에서 IDE사용없이 자체 사이트에서 코드를 작성해야 해서 막막할 수 있음
  • 프로그래머스에도 Lv. 컨텐츠가 있지만, 레벨별 난이도 차이가 들쑥날쑥하다고 생각

풀이과정 및 리뷰

• 문제 접근: before의 회의종료 시간과, after의 회의시작 시간을 비교해서 after.start ≥ before.end시간이라면 시간이 겹치지 않고 회의를 배정할 수 있다고 판단했음

  또한, 이렇게 리스트를 비교해나가기 위해선 정렬이 필요하다고 생각했고, 끝나는 시간이 빠른순(테케에 힌트가 있었다..) → 시작시간이 빠른순으로 정렬하여 순회하는것이 제일 효율적

(처음 삽질)

end - start의 회의에 걸리는 시간을 기준으로 정렬하여 before.end / after,start를 비교해 겹치지 않는 회의 개수를 카운트 하려고 했음

Map<Integer,Integer>에 시작 / 종료 시간을 넣어 시작시간기준 제일 빠른 종료시간을 맵에서 갱신해 갯수를 세려고 함

(문제점) 4/4로 끝나는 경우와 4/5 등이 함께 있을경우 회의시간이 0시간인 회의에 대해++ 해준 후 4/5를 선택해야 하는데, end - start시간이 가장 작은 값만 담아 카운트가 제대로 되지 않음. 그래서 start=end인 회의에 대해 맵에 넣지 않고 무조건 cnt먼저 ++ 해둔후 1이상 차이나는 가장 작은 값만 넣으려 함 → 이랬더니, 해당 시간이 아닌 경우로 회의를 배정했을 때 회의 수가 가장 큰 경우의 처리가 불가능해서 포기 

• 시간복잡도: $O(N Log N)$

  Collections.sort(list) O(N log N) + 리스트 순회 O(N)

• 풀이과정

  • Room 클래스 생성

    -Comparable을 구현하여 끝나는 시간(같다면 시작시간) 기준으로 정렬

  • 메인에서 리스트 순회하며 target(직전 회의 끝나는시간)과 직후 회의의 시작시간을 비교하여 겹치지 않는 회의수 카운트

• 개선점

compareTo 대신 Comparator 활용

• Comparable을 구현하면 한 가지 기준으로만 정렬됩니다.
• 경우에 따라 다른 기준 정렬을 하고 싶을 땐 Comparator를 쓰는 게 더 유연해요.

list.sort((a, b) -> {
    if (a.end == b.end) return a.start - b.start;
    return a.end - b.end;
});
→ 이렇게 하면 `Room`에 불필요하게 `Comparable`을 구현하지 않아도 됨

Room 클래스 불변성 확보

• start와 end는 회의 시간으로 변경될 일이 없으므로 final로 선언하는 게 안전.

class Room {
    final int start;
    final int end;

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

정렬 안정성 보장

• 현재 compareTo 구현은 잘 돼 있지만, this.start - other.start 같은 뺄셈 연산은 오버플로우 위험이 있어요.

  → Integer.compare(this.start, other.start)를 쓰면 안전합니다.

list.sort((a, b) -> {
    int cmp = Integer.compare(a.end, b.end);
    if (cmp == 0) return Integer.compare(a.start, b.start);
    return cmp;
});

기타

Java에서 Collections.sort() 동작 방식

• Collections.sort(List<T> list) → 내부적으로 list.toArray()를 호출해서 배열로 바꾼 다음,

  Arrays.sort()를 실행

• 따라서 실제 정렬 알고리즘은 Arrays.sort()가 무엇을 쓰는지에 따라 결정됨

✅ 구체적으로

1. Primitive 타입 배열 (int[], double[] 등)

   • Dual-Pivot Quicksort (이중 피벗 퀵정렬) 사용
   • 시간 복잡도: 평균 O(N log N), 최악 O(N²)
   • 다만 구현이 잘 돼 있어서 실제로는 굉장히 빠름

2. 객체 배열 (Integer[], String[], Room[] 등 Comparable 구현 객체)

   • Java 7 이후 → TimSort 사용

     (Merge Sort + Insertion Sort를 합친 하이브리드 정렬 알고리즘)

   • 시간 복잡도:

     • 최악: O(N log N)
     • 최선(이미 정렬된 경우): O(N)

   • 안정 정렬(Stable Sort) → 같은 값일 경우 기존 순서 유지.

3. 즉, Collections.sort(list)는

   • 내부적으로 list.toArray() → Arrays.sort(Object[]) → TimSort 순서로 동작.
   • 따라서 객체 리스트 정렬은 항상 안정 정렬

📌 정리

• Collections.sort(list) → 내부적으로 Arrays.sort() 호출.
• Primitive 배열: Dual-Pivot QuickSort.
• 객체 배열: TimSort (안정 정렬, O(N log N)).
• 실무에서 List 정렬 시 대부분 TimSort

TimSort란?

병합정렬 + 삽입정렬 방법으로, 크기가 작은 배열에서는 삽입정렬을 이용하고 크기가 큰 경우 병합정렬을 사용한다. 그래서 하이브리드 정렬이라고도 부른다.

삽입 정렬 (Insertion Sort)

개념

• 손으로 카드를 정렬하는 방식과 비슷
• 배열을 앞에서부터 순회하며 현재 원소를 알맞은 위치에 끼워 넣는 방식

배열: [5, 2, 4, 6, 1, 3]

1단계: 2 → [2, 5, 4, 6, 1, 3]
2단계: 4 → [2, 4, 5, 6, 1, 3]
3단계: 6 → [2, 4, 5, 6, 1, 3]
4단계: 1 → [1, 2, 4, 5, 6, 3]
5단계: 3 → [1, 2, 3, 4, 5, 6]

병합 정렬 (Merge Sort)

개념

• 분할 정복(Divide and Conquer) 방식
• 배열을 반으로 쪼개고, 각각 정렬 후 병합

  배열: [5, 2, 4, 6, 1, 3]
  

분할: [5, 2, 4] [6, 1, 3] 분할: [5] [2, 4] ... → 재귀적으로 정렬 병합: [2, 4, 5] [1, 3, 6] → 최종 병합 → [1, 2, 3, 4, 5, 6] ```

풀이과정 및 리뷰

1. boolean[][] home - 1인 경우 true 저장하는 집 배열, boolean[][] visited - 방문 여부 저장할 배열, int[][] dir - 상하좌우 탐색할 배열, List<Integer> list - 단지별 집 수를 오름차순으로 정렬하기 위한 리스트 선언

2. bfs 내부에서 인접 4방향 탐색하며 방문하지 않았고&& home == true 인 경우 큐에 넣어가며 큐가 빌 때까지 탐색, 더이상 아무 인접 지점도 두 조건을 충족하지 못하는 경우 메서드 종료

3. 메인 메서드 내에서 2차원 배열 루프를 돌며 방문하지 않았고 && home == true인 경우 bfs를 호출하여 리턴값을 리스트에 저장 + 단지 수 카운트 homes++

   → 즉 메인 함수는 bfs가 인접지역에서 더이상 방문하지 않은 집을 못찾은 경우, 위치를 옮겨 다시 조건을 만족하는 지점을 찾아 탐색하기 위함임

풀이과정 및 리뷰

1. 입력값(지형의 높이)을 받을 int[][] area , 방문여부 저장할 boolean[][] visited , 침수 여부 저장할 boolean[][] wet 배열 선언

   → 이때, area를 제외한 visited / wet 2차원배열은 비의 높이(0~최대높이-1)가 바뀔때마다 초기화됨

2. dfs(boolean[][] visited, boolean[][] wet, int r, int c) 메서드를 이용해 비의 높이별 visited / wet 배열의 방문여부 / 침수여부를 업데이트함 + wet[r][c] && !visited[r][c] 조건을 충족하는 좌표 (r,c)의 4방향을 탐색함

   → 흐름

   1. 2차원배열 For문 안에서, 젖지 않았고 방문하지 않은 좌표를 발견하면 dfs 호출
   2. 함수 내부에서 4방향 탐색을 하면서, 주위 4방향에 젖지 않은 지역이 있을때마다 재귀호출
   3. 주위 4방향에 침수된 지역밖에 없다면 메서드가 종료되며 count가 올라감

리뷰

문제점 1. boolean[][] wet 배열은 사실 젖지 않은 지역이 true로 저장된다….헷갈리게 변수명을 설정함

문제점 2. 코드 길이가 너무 길다..그에 비해 실행시간은 짧은 점은 놀랍다.

아쉬운 점.

1. wet배열을 반대로 생각해 젖은 지역을 true로 설정했다면, 매 rain마다 배열을 초기화 할 필요 없이 재사용(값 덮어쓰기)가 가능했음
2. 비의 높이가 ‘비가 내리지 않는 경우도 있다’는 조건때문에, 0~ maxH-1까지 탐색했지만, 어느 로직을 적용해 최적의 비높이 사이에서만 For문을 반복하는 방법이 있을 것도 같다..(못찾음ㅎ)

풀이과정 및 리뷰

1. 퍼지는 문제이므로 인접노드들을 모조리 큐에 넣어서 탐색하면서 카운트하기 위해 bfs 사용

2. 무방향 그래프이므로 양방향의 인덱스에 값을 모두 추가해 연결

3. 1에서 시작하면서, 1은 카운트 하지않으므로 큐에 인접노드를 집어넣는 시점에 ++cnt 하고,

   큐가 비어 while문을 빠져나오면 cnt를 반환하도록 함

풀이과정 및 리뷰

1. 우선 N / K 를 입력받은 후 bfs의 파라미터로 N을 넘김(int start)

2. 이때 N == K 라면 0을 리턴하고 바로 종료

3. bfs메서드 호출

   • 100,001개의 visited - 방문여부 체크 / distance - 해당 지점까지의 최단거리 저장하는 배열 선언

   • q에 시작점을 넣고 방문체크

   • 큐가 빌때까지 큐에서 데이터를 꺼내 n+1 / n-1 / 2 * n한 next 값들을 차례로 순회하며, 방문하지 않은 경우에 한해(인덱스초과 에러 방지 조건 추가) 미리 방문체크 및 최단 카운트 저장

   • next값을 큐에 저장해 연산 계속 수행

   • 이때, if(next == K) return distance[next] 코드가 존재하지 않아도 메인에서 sysout(distance[K] 로 값을 찾을 수 있음.

     → K에 도달하는 최단거리를 구하기 위해 bfs를 사용했는데, bfs는 인접노드부터 탐색하므로 next == K를 만나서 리턴해도 결과값은 같음

리뷰

if(next == K) return distance[next]

next == K일 때 바로 return 하는 건 BFS에서는 맞고, DFS에서는 틀릴 수 있다.

BFS (Breadth-First Search)

• 최단 거리 보장 O → 즉 처음 발견하는 순간이 최단거리
• 큐를 사용해서 레벨 순서대로 탐색
• 먼저 도착한 경로가 곧 최단 경로
• 그래서 next == K일 때 바로 리턴해도 안전

❌ DFS (Depth-First Search)

• 최단 거리 보장 안 됨 X → DFS에선 끝까지 다 탐색하고, 가장 짧은 거리만 골라야 함
• 스택 또는 재귀로 한쪽 끝까지 파고듦
• 먼저 도착한 경로가 최단일 가능성이 없음
• 그래서 next == K에서 바로 return 하면 틀릴 수 있음

풀이과정 및 리뷰

1. 촌수 계산 ⇒ 시작점에서 도착점까지 도달하는 최단거리가 촌수이므로 bfs로 최단거리 찾기 시작
2. 노드 연결관계 저장할 List<Integer>[] graph , 방문여부 저장할 boolean[] visited, 타켓(시작점)에서 목적지까지 도달하는데 걸리는 거리 저장할 int[] target 배열 선언
3. bfs선언
   • 일단 출발지 방문체크 후 큐에 넣음
   • 큐가 빌 때까지 반복
     • 이전 노드와 연결된 지점들 중 방문하지 않은 노드 탐색
     • 방문하지 않았을 경우 방문체크후 큐에 삽입
     • target[next] 인덱스에 이전 prev 인덱스 + 1값 저장해 최단거리 계산
     • sysout에서 한번에 존재/존재X시의 값 리턴 위해, next == ch(목적지) 조건에 걸리는 경우 target[next]를 리턴하도록 코드 추가

풀이과정 및 리뷰

1. 1 인 경우 true 값을 가지는 boolean[][] maze , 방문여부 확인할 boolean[][] visited 생성

2. 상하좌우로만 인접한 경우에 해당해 전진할 수 있으므로 4방향 배열 생성

3. r, c, count를 인자로 받는 bfs 메서드 선언

   • (r,c,count)배열을 큐에 저장 → 꺼내서 주위 4방향 탐색해 maze[nr][nc] = true 라면 방문체크 및

     큐에 다시 넣어서 큐가 빌 때까지 순회하도록 함

4. 처음과 끝점도 카운트에 포함되므로, 첫인자로 0,0,2를 넘긴다.

중대한 오류와 보완점

System.out.println(bfs(0,0,2)); 로 시작할때 count 2로 넘김

→ 잘 생각해보면, 끝점은 bfs메서드 안에서 지나면서 count+1될 것이므로 (0,0,1)을 인자로 넘겼어야 했음.

bfs 메서드 안의 if(nr == N-1 && nc == M -1) return cnt++; 에서 내 의도는 return cnt+1 이었지만, 후위연산자여서 cnt값을 반환하고 cnt+1은 버려지므로 이 두개의 잘못된 코드가 맞물려 결과적으로는 맞았지만,

올바르게 고치면 System.out.println(bfs(0,0,1)); , if(nr == N-1 && nc == M -1) return cnt+1; 로 적었어야 했다.

요약

오류 : 시작점부터 cnt = 2로 시작점과 끝점을 모두 카운트 한채로 bfs 돌았음 + 도착점에서 후위연산자 착각해서 결과적으로 cnt+1 이 아닌 cnt 가 반환됨. → 시작에서 1크게, 끝에서 1작게 코드를 작성해서 아다리는 맞았지만 내 의도와는 맞지 않았음

수정 : 시작점에서 cnt = 1 로 시작해서 시작점만 밟은 채로 순회 시작 + 도착점 도달시 cnt+1 되게 수정

최종 수정본

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

class Main {
    static int[][] dist = {
            {-1,0},{1,0},{0,-1},{0,1}};
    static int N;
    static int M;
    static boolean[][] maze;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        maze = new boolean[N][M];
        for(int i = 0; i < N; i++){
            String s = br.readLine();
            for(int j = 0; j < M; j++){
                maze[i][j] = ( (s.charAt(j) - '1' == 0));
            }
        }
        visited = new boolean[N][M];
        System.out.println(bfs(0,0,1));
    }
    static int bfs(int i, int j, int count){
        visited[i][j] = true;
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {i,j,count});

        while(!q.isEmpty()) {
            int[] a = q.poll();
            int r = a[0]; int c = a[1]; int cnt = a[2];
            for (int d = 0; d < 4; d++) {
                int nr = r + dist[d][0];
                int nc = c + dist[d][1];

                if (nr >= 0 && nc >= 0 && nr < N && nc < M
                        && !visited[nr][nc] && maze[nr][nc]) {
                    if(nr == N-1 && nc == M -1) return cnt + 1;
                    visited[nr][nc] = true;
                    q.add(new int[] {nr,nc,cnt+1});
                }
            }
        }
        return -1;
    }
}

풀이과정 및 리뷰

1. 0 0 이 들어오면 종료되므로,

   String a = ""; while (!(a = br.readLine()).equals("0 0") 로 조건 만족시 반복문 안 돌도록

2. 처음 2차원 배열 섬 입력을 받을때 1인 경우 true로 받는 boolean[][] island 생성 및 초기화

3. 대각선으로 이어져있어도 섬으로 인정되므로 8방탐색 배열 선언

4. 이미 방문한 곳을 제외하기 위한 boolean[][] visited 생성 및 초기화

5. 처음 dfs내부에서 섬 개수를 count 로 받아 매 호출마다 ++ 하려고 했지만, 디버깅이 어렵고 흐름따라가기가 어려워 아예 메인함수로 빼버림

6. DFS

• 일단 시작점 visited = true 로 변경 후, 인접 8방향 탐색 시작
• 배열을 벗어나지 않음 && 방문한적 없음 && 섬인 경우 재귀호출
• 종료조건 : 배열을 벗어나거나, 방문한 노드거나, 섬이 아닌 경우

1. dfs의 재귀호출이 종료되면, 메인함수 내부에서 루프를 돌며 섬인 경우 && 방문하지 않은 경우에 해당하는

   노드를 찾아 dfs를 재호출

→ 이때, dfs가 호출되고 연결된 지점이 없어 메서드가 종료되면 count가 올라가는 식으로 로직을 짬

보완점

1. null 체크 → 해당 문제는 해당없음

• while (!(a = br.readLine()).equals("0 0"))
• 입력이 "0 0"이면 종료하도록 잘 처리했는데, 만약 입력이 없거나 파일 끝(EOF)일 때 br.readLine()이 null이 될 수 있습니다. null 체크도 넣으면 더 안정적입니다.

1. 방문 체크 시점

• visited[r][c] = true;는 dfs 초반에 해주셨는데, 중복 방문을 막기 위해 dfs 호출 직전에 하는 것도 안전합니다.