[프로그래머스 SQL] 멸종위기의 대장균 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/301651

프로그래머스

 

코드

WITH RECURSIVE ECOLI_HIERACHY AS (
    SELECT ID, PARENT_ID, 1 AS GENERATION
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL

    UNION ALL
    
    SELECT E.ID AS ID, EH.ID AS PARENT_ID, EH.GENERATION + 1 AS GENERATION
    FROM ECOLI_HIERACHY EH JOIN ECOLI_DATA E ON EH.ID = E.PARENT_ID
)

SELECT COUNT(*) AS COUNT, GENERATION
FROM ECOLI_HIERACHY
WHERE ECOLI_HIERACHY.ID NOT IN (SELECT EH1.ID AS ID
    FROM ECOLI_HIERACHY EH1 JOIN ECOLI_HIERACHY EH2 ON EH1.ID = EH2.PARENT_ID)
GROUP BY GENERATION
ORDER BY GENERATION
    

 

쿼리 실행 순서

순서	실행 단계	설명
1	WITH RECURSIVE 실행	ECOLI_HIERARCHY CTE(Common Table Expression)를 생성
1.1	기본 선택 (SELECT ... WHERE PARENT_ID IS NULL)	PARENT_ID IS NULL 인 루트 노드를 가져옴
1.2	재귀적으로 자식 노드 추가 (JOIN 사용)	ECOLI_HIERARCHY에서 부모 ID를 찾아 자식 노드를 추가
2	WHERE 서브쿼리 실행	ECOLI_HIERARCHY.ID NOT IN (...) 를 해결하기 위해 내부 서브쿼리 실행
3	서브쿼리 JOIN 실행	부모 노드를 찾기 위해 ECOLI_HIERARCHY를 자기 자신과 조인
4	WHERE 조건 적용	부모 노드가 아닌(자식이 없는) 행들만 필터링
5	GROUP BY GENERATION 실행	같은 GENERATION 값을 가진 행들을 그룹화
5	COUNT(*) 집계 함수 실행	그룹별 행 개수 계산
7	ORDER BY GENERATION 실행	GENERATION 값을 기준으로 정렬

 

풀이

현재 주어진 테이블 옆에 세대를 나타내는 컬럼이 추가되기만 하면 SELF JOIN을 통해서 자식이 없는 대장균을 찾을 수 있습니다.

따라서 세대 컬럼을 재귀 CTE로 계산해서 만들어주기로 했습니다.

 

WITH RECURSIVE

재귀 CTE(Common Table Expression)는 자기 자신을 반복적으로 호출하여 계층적 데이터(tree, graph)를 탐색하는 데 유용합니다.

 

1. 기본 개념 (WITH RECURSIVE의 작동 원리)

재귀 CTE의 구성 요소

WITH RECURSIVE는 두 개의 부분으로 구성됩니다:

1️⃣ Anchor (기본 쿼리)

• 루트 데이터(최상위 계층)를 찾는 역할
• 보통 WHERE PARENT_ID IS NULL 같은 조건을 사용

2️⃣ Recursive (재귀 쿼리)

• 자기 자신을 호출하며 계층을 확장
• JOIN을 사용하여 자식 데이터를 계속 추가

3️⃣ UNION ALL

• 기본 쿼리와 재귀 쿼리를 결합하여 전체 트리 구조 생성

---

2. 재귀 CTE의 실행 과정

sql
복사편집
WITH RECURSIVE example_hierarchy AS (
    -- 기본 루트 노드 선택 (PARENT_ID가 NULL)
    SELECT ID, PARENT_ID, 1 AS LEVEL
    FROM example_table
    WHERE PARENT_ID IS NULL

    UNION ALL

    -- 자기 자신과 JOIN하여 재귀적으로 자식 노드 찾기
    SELECT e.ID, e.PARENT_ID, eh.LEVEL + 1
    FROM example_table e
    JOIN example_hierarchy eh ON e.PARENT_ID = eh.ID
)

-- 최종 결과 출력 (계층 구조 정렬)
SELECT * FROM example_hierarchy ORDER BY LEVEL, ID;

---

3. 실행 흐름 이해하기

예제 데이터: example_table

ID	PARENT_ID
1	NULL
2	1
3	1
4	2
5	2
6	3
7	6

---

실행 과정 (재귀적으로 확장됨)

단계	실행 결과 (ID, PARENT_ID, LEVEL)
1. Anchor 실행 (루트 노드)	(1, NULL, 1)
2. 1을 부모로 하는 자식 찾기	(2, 1, 2), (3, 1, 2)
3. 2를 부모로 하는 자식 찾기	(4, 2, 3), (5, 2, 3)
4. 3을 부모로 하는 자식 찾기	(6, 3, 3)
5. 6을 부모로 하는 자식 찾기	(7, 6, 4)
6. 최종 결과	계층적으로 모든 노드 탐색 완료

 

최종 결과 (ORDER BY LEVEL, ID)

ID	PARENT_ID	LEVEL
1	NULL	1
2	1	2
3	1	2
4	2	3
5	2	3
6	3	3
7	6	4

---

4. WITH RECURSIVE의 핵심 특징

✔ 재귀적으로 호출: 자식 노드를 계속 찾아나감

✔ LEVEL을 이용한 깊이 계산 가능

✔ 트리 및 계층 구조 탐색에 적합

✔ 루트부터 시작하여 모든 연결된 노드를 찾음

---

5. 예제 2: 조직도 (부서 계층 구조)

WITH RECURSIVE org_chart AS (
    -- CEO 찾기 (최상위 노드)
    SELECT EMP_ID, MANAGER_ID, 1 AS LEVEL
    FROM EMPLOYEES
    WHERE MANAGER_ID IS NULL

    UNION ALL

    -- 재귀적으로 직속 부하직원 찾기
    SELECT e.EMP_ID, e.MANAGER_ID, oc.LEVEL + 1
    FROM EMPLOYEES e
    JOIN org_chart oc ON e.MANAGER_ID = oc.EMP_ID
)

-- 계층적 조직도 출력
SELECT * FROM org_chart ORDER BY LEVEL, EMP_ID;

 

예제 데이터

EMP_ID	MANAGER_ID
1	NULL
2	1
3	1
4	2
5	2
6	3
7	6

실행 결과

 

EMP_ID	MANAGER_ID	LEVEL
1	NULL	1
2	1	2
3	1	2
4	2	3
5	2	3
6	3	3
7	6	4