[프로그래머스 Level.4] 특정 세대의 대장균 찾기

문제

대장균들은 일정 주기로 분화하며, 분화를 시작한 개체를 부모 개체, 분화가 되어 나온 개체를 자식 개체라고 합니다.
다음은 실험실에서 배양한 대장균들의 정보를 담은 ECOLI_DATA 테이블입니다. ECOLI_DATA 테이블의 구조는 다음과 같으며, ID, PARENT_ID, SIZE_OF_COLONY, DIFFERENTIATION_DATE, GENOTYPE 은 각각 대장균 개체의 ID, 부모 개체의 ID, 개체의 크기, 분화되어 나온 날짜, 개체의 형질을 나타냅니다.

Column Name	Type	Nullable
ID	INTEGER	FALSE
PARENT_ID	INTEGER	TRUE
SIZE_OF_COLONY	INTEGER	FALSE
DIFFERENTIATION_DATE	DATE	FALSE
GENOTYPE	INTEGER	FALSE

최초의 대장균 개체의 PARENT_ID 는 NULL 값입니다.

[문제]

3세대의 대장균의 ID(ID) 를 출력하는 SQL 문을 작성해주세요. 이때 결과는 대장균의 ID 에 대해 오름차순 정렬해주세요.

[예시]

예를 들어 ECOLI_DATA 테이블이 다음과 같다면

ID	PARENT_ID	SIZE_OF_COLONY	DIFFERENTIATION_DATE	GENOTYPE
1	NULL	10	2019/01/01	5
2	NULL	2	2019/01/01	3
3	1	100	2020/01/01	4
4	2	16	2020/01/01	4
5	2	17	2020/01/01	6
6	4	101	2021/01/01	22
7	3	101	2022/01/01	23
8	6	1	2022/01/01	27

PARENT ID 가 NULL 인 ID 1, ID 2가 1 세대이며 ID 1에서 분화된 ID 3, ID 2에서 분화된 ID 4, ID 5 가 2 세대입니다. ID 4 에서 분화된 ID 6, ID 3에서 분화된 ID 7 이 3 세대이며 ID 6에서 분화된 ID 8은 4 세대입니다.

따라서 결과를 ID 에 대해 오름차순 정렬하면 다음과 같아야 합니다.

ID
6
7

소스코드

WITH RECURSIVE GENERATIONS AS (
    -- Anchor Member: 최상위 부모를 선택합니다.
    SELECT
        ID,
        PARENT_ID,
        1 AS GENERATION
    FROM
        ECOLI_DATA
    WHERE
        PARENT_ID IS NULL
    
    UNION ALL
    
    -- Recursive Member: 자식을 찾아 다음 세대로 이동합니다.
    SELECT
        E.ID,
        E.PARENT_ID,
        G.GENERATION + 1 AS GENERATION
    FROM
        ECOLI_DATA AS E
    JOIN
        GENERATIONS AS G
    ON
        E.PARENT_ID = G.ID
)

-- 3세대에 해당하는 ID를 선택하고 정렬합니다.
SELECT
    ID
FROM
    GENERATIONS
WHERE
    GENERATION = 3
ORDER BY
    ID;

배운점

WITH RECURSIVE는 SQL에서 재귀적 CTE (Common Table Expression)를 정의하는 데 사용됩니다. 이를 통해 쿼리는 자기 자신을 참조하여 반복적으로 실행될 수 있습니다. 재귀적 CTE는 트리나 계층 구조 데이터를 처리하는 데 유용합니다.

구성 요소

재귀적 CTE는 두 부분으로 구성됩니다:
1. Anchor Member: 재귀의 초기 상태를 정의하는 쿼리입니다. 이 쿼리는 재귀의 기초가 되는 행들을 반환합니다.
2. Recursive Member: 이전에 반환된 행을 기반으로 새로운 행을 생성하는 쿼리입니다. 이 쿼리는 재귀적으로 반복 실행됩니다.

구조

일반적인 WITH RECURSIVE 구문은 다음과 같습니다:

WITH RECURSIVE cte_name (column1, column2, ...) AS (
    -- Anchor Member
    SELECT initial_columns
    FROM initial_table
    WHERE condition
    
    UNION ALL
    
    -- Recursive Member
    SELECT next_columns
    FROM next_table
    JOIN cte_name ON condition
)

-- Query that uses CTE
SELECT *
FROM cte_name;

예제

직원 테이블에서 계층 구조를 표현하는 예제를 보겠습니다

employee_id	employee_name	manager_id
1	Alice	NULL
2	Bob	1
3	Charlie	1
4	David	2
5	Eve	2

WITH RECURSIVE employee_hierarchy AS (
    -- Anchor Member: 최상위 관리자를 찾습니다.
    SELECT employee_id, employee_name, manager_id, 1 AS level
    FROM employees
    WHERE manager_id IS NULL
    
    UNION ALL
    
    -- Recursive Member: 직원의 계층을 탐색합니다.
    SELECT e.employee_id, e.employee_name, e.manager_id, eh.level + 1
    FROM employees e
    JOIN employee_hierarchy eh ON e.manager_id = eh.employee_id
)
SELECT *
FROM employee_hierarchy;

결과

이 쿼리는 직원 테이블의 계층 구조를 탐색하여 모든 직원과 그들의 계층 수준을 반환합니다:

employee_id	employee_name	manager_id	level
1	Alice	NULL	1
2	Bob	1	2
3	Charlie	1	2
4	David	2	3
5	Eve	2	3

주의 사항

• UNION ALL을 사용하여 모든 반복 결과를 포함합니다. UNION은 중복 행을 제거하지만, 재귀 쿼리에서는 일반적으로 UNION ALL이 사용됩니다.
• 재귀적 CTE는 무한 루프에 빠질 수 있으므로 적절한 종료 조건이 필요합니다. 대부분의 데이터베이스는 이를 방지하기 위해 최대 재귀 깊이를 설정할 수 있습니다.