[MySQL] 멸종위기의 대장균 찾기

문제 설명

 

문제

---

풀이(답)

WITH RECURSIVE generations AS (  # 1. 재귀함수 정의
	SELECT				# 2. Anchor member: 부모가 없는(최초) 1 세대
    	id,
        parent_id,
        1 AS generation		# 3. 1 세대를 의미
    FROM ECOLI_DATA
    WHERE parent_id IS NULL 	# 4. 부모가 NULL이면 최상위 세대
    
    UNION ALL					# 5. Anchor 결과와 Recursive 결과를 합침
    
    SELECT				# 6. Recursive member: 이미 찾은 세대의 자식들을 찾아 세대를 +1 해가며 확장
    	child.id,
        child.parent_id
        parent.generation + 1 as generation	# 7. 부모 세대 +1 을 자식 세대로 지정
    FROM ECOLI_DATA AS child JOIN generations as parent ON child.parent_id = parent.id
    # 8. 전체 데이터(child)에서 기존의 계산된 generations(parent)의 id와 child.parent_id가 
    # 일치하는 자식만 선택
)
# 9. 재귀 완성 후, generations를 이용해 결과 조회
SELECT
	COUNT(*) AS COUNT
    g.generation AS GENERATION
FROM generations AS g
WHERE NOT EXISTS (	# 10. NOT EXISTS를 사용해 '자식이 없는' 레코드만 걸러냄
	SELECT GENERATION
    FROM ECOLI_DATA AS e2
    WHERE e2.parent_id = g.id	# 11. 이 ID를 부모로 가진 레코드가 하나도 없는 경우
)
GROUP BY g.generation
ORDER BY g.generation

---

📌 문제에 대한 접근 방법

이 문제는 ECOLI_DATA 테이블에서 계층 구조(부모-자식 관계)를 다뤄야 하는 문제이다. 특히, 특정 개체의 자식 세대가 여러 단계로 확장되어 있어서 몇 세대까지 존재할지 모르는 경우, 단순 JOIN만으로는 처리하기 어렵다.

이런 상황에서는 다음의 두 가지를 활용한다:

• WITH RECURSIVE
  깊이를 알 수 없는 트리 구조(부모-자식 관계)를 SQL만으로 해결할 때 사용하는 방법이다. 최초 기준(부모가 없는 개체)을 세우고, 자기 자신과 JOIN을 반복(재귀 호출)하면서 다음 세대, 그 다음 세대까지 무한히 확장해 나갈 수 있다.
• UNION ALL
  위에서 만든 최초 기준(Anchor member)의 결과와 재귀 호출(Recursive member)의 결과를 하나로 합치는 역할을 한다.
  UNION ALL은 단순히 결과를 붙이는 연산으로 중복 제거가 없기 때문에, 각 세대가 정확히 한번씩만 등장하는 이 문제에서 적합하다.

---

📌 코드 한 줄씩 상세히 복기하기 

🔍 WITH RECURSIVE 재귀함수 정의

• 2~4번째 줄 (Anchor Member)
  parent_id가 NULL인 개체들은 최초의 개체, 즉 1세대임을 의미한다. 최초 개체의 generation을 1로 지정하고, 이들을 재귀의 기준(Anchor member)으로 삼는다.
• 5번째 줄 (UNION ALL)
  Anchor에서 나온 1세대 결과와 아래에서 계속 찾을 자식 세대들을 모두 합치기 위해 사용한다.
• 6~8번째 줄 (Recursive Member)
  이미 찾은 세대의 결과(generations)와 원본 데이터를 JOIN 하면서 다음 세대를 찾아가는 과정이다. JOIN 조건은 원본 테이블의 child.parent_id와 이미 찾은 부모 세대의 parent.id가 같아야 한다. 즉, “부모 세대와 자식 세대를 연결”해가는 과정이며, 세대를 하나씩 증가(parent.generation + 1)시키며 확장해간다.

이렇게 Anchor member(최초 세대)와 Recursive member(이후 모든 세대)가 계속 반복되면서, 전체 세대를 모두 찾아 generations 라는 임시 테이블이 만들어진다.

---

🔍 결과 조회 및 NOT EXISTS로 자식 없는(leaf) 개체 필터링

• 9번째 줄 (재귀 결과 활용)
  재귀 호출로 완성된 전체 세대 데이터를 이제 실제 필요한 형식으로 가공하여 출력한다.
• 10~11번째 줄 (NOT EXISTS)
  이 문제에서는 “자식이 없는 개체”를 찾는 게 핵심이다.
  여기서 NOT EXISTS는 하위 쿼리 결과가 하나도 없는 경우에만 참(True)을 반환한다. 즉,

SELECT 1 FROM ECOLI_DATA AS e2 WHERE e2.parent_id = g.id

위 서브쿼리가 의미하는 건, 현재 개체(g.id)를 부모로 가진 자식 개체가 존재하는지를 검사하는 것이다.

 

g.id	e2.parent_id 존재 여부	EXISTS 결과	NOT EXISTS 결과
1	X (자식 없음)	FALSE	TRUE ✅
2	O (자식 있음: 3,4,5)	TRUE	FALSE ❌
3	X (자식 없음)	FALSE	TRUE ✅
4	O (자식 있음: 6,7)	TRUE	FALSE ❌
5	X (자식 없음)	FALSE	TRUE ✅
6	O (자식 있음: 8)	TRUE	FALSE ❌
7	X (자식 없음)	FALSE	TRUE ✅
8	X (자식 없음)	FALSE	TRUE ✅

위 표를 보면 명확히 알 수 있듯, NOT EXISTS를 통해 자식이 없는(leaf) 개체만 걸러서 선택된다.

---

🔍 최종 집계와 정렬

• 위에서 걸러낸 자식이 없는 개체들을 세대별로(GROUP BY g.generation) 몇 개인지 카운트하고(COUNT(*)),
• 세대를 오름차순으로(ORDER BY g.generation) 정렬하여 최종 결과를 얻는다.

---

📌 언제 이 방법을 써야 하나?

데이터베이스 테이블이 자기 자신을 참조하는 계층 구조를 가질 때, 특히 깊이를 알 수 없는 경우에 자주 사용한다.

대표적 예시:

• 회사의 조직도(CEO → 부장 → 과장 → 사원)
• 게시글의 댓글과 답글 관계
• 대장균처럼 분화되어 계속 이어지는 세대 관계(이 문제와 동일한 경우)

이러한 상황에서 WITH RECURSIVE + UNION ALL + NOT EXISTS를 사용하면 효율적이고 직관적인 SQL 쿼리를 작성할 수 있다.

---

✅ 결론적으로 다시 요약하면

• 계층 구조 데이터를 다룰 때 → WITH RECURSIVE를 사용.
• 최초 기준(Anchor)을 세우고, 자식 세대(Recursive)를 찾아 내려가며 반복 확장.
• 두 결과를 UNION ALL로 합쳐 모든 세대를 동적 생성.
• 최종적으로 자식 없는 leaf 개체는 NOT EXISTS로 필터링하여 최종 결과를 도출.