BOJ 풀이 노트: 트리 부모 탐색과 상담 스케줄 DP 점검

2026. 3. 4. · tech

BOJ 11725와 15486 풀이를 중심으로 루트 트리 부모 기록 방식, 날짜 축 기준 최대 이익 DP 설계를 실전 포인트 위주로 정리했다.

오늘은 그래프/트리 계열 1문제와 DP 1문제를 묶어서 풀었다.

• BOJ 11725 - 트리의 부모 찾기
• BOJ 15486 - 퇴사 2

한 문제는 루트 기준 관계를 빠르게 정리하는 문제, 다른 문제는 날짜 축에서 가능한 최대 수익을 누적하는 문제라서 결이 다르다. 하루 2문제 루틴에서 유형 분산하기에 좋은 조합이었다.

1) BOJ 11725 - 트리의 부모 찾기

문제 핵심 요약

루트가 1번인 트리에서 2번 노드부터 N번 노드까지 각 노드의 부모를 출력하는 문제다.

접근 아이디어(왜 이 방법인지)

트리는 사이클이 없고, 루트에서 한 번만 방문하면서 내려가면 각 노드의 부모가 자연스럽게 정해진다. BFS(또는 DFS)로 1번에서 시작해 처음 방문한 순간의 이전 노드를 부모로 기록하면 된다.

이 방식은 간선 수가 N-1인 트리 구조와 잘 맞고, 구현도 단순하다.

시간/공간 복잡도

• 시간: O(N)
• 공간: O(N)

실수하기 쉬운 포인트

• 방문 배열 대신 부모 배열을 쓰면서 초기값 처리를 애매하게 하는 실수
• 루트(1번)의 부모를 출력 대상으로 착각하는 실수
• 입력이 무방향 간선인데 한쪽만 저장하는 실수

C++ 코드 설명(핵심 라인)

queue<int> q;
q.push(1);
parent[1] = -1;

1번 노드를 시작점으로 넣고, 루트는 재방문 방지를 위해 미리 표시한다.

for (int nxt : graph[cur]) {
    if (parent[nxt] != 0) continue;
    parent[nxt] = cur;
    q.push(nxt);
}

아직 부모가 정해지지 않은 이웃만 방문하면서 현재 노드를 부모로 기록한다.

다른 풀이 가능성

• 재귀 DFS로도 동일하게 해결 가능하다.
• 입력 크기에 따라 재귀 깊이가 부담될 수 있어, 반복형 BFS/스택 DFS가 더 안전한 선택일 때가 많다.

2) BOJ 15486 - 퇴사 2

문제 핵심 요약

각 날짜마다 상담 기간(T[i])과 보상(P[i])이 주어질 때, 퇴사일 전까지 가능한 상담을 선택해 최대 수익을 구하는 문제다.

접근 아이디어(왜 이 방법인지)

핵심은 날짜를 왼쪽에서 오른쪽으로 진행하면서 그 날짜까지 확보 가능한 최대 수익을 유지하는 것이다.

• dp[d]: d일 시작 시점(또는 d일 직전까지) 확보 가능한 최대 수익
• 오늘 상담을 하지 않으면 다음 날로 현재 최댓값을 넘긴다.
• 오늘 상담을 하면 종료 다음 날 위치에 이익을 반영한다.

이렇게 하면 각 날짜를 한 번씩만 처리해 O(N)에 끝난다.

시간/공간 복잡도

• 시간: O(N)
• 공간: O(N)

실수하기 쉬운 포인트

• 상담 종료일/보상 반영일 인덱스를 하루씩 틀리는 오프바이원
• N이 커서 int 누적값이 불안할 수 있는데 자료형을 너무 작게 잡는 실수
• dp[day] = max(dp[day], dp[day-1]) 전달 갱신을 빼먹어 최댓값 전파가 끊기는 실수

C++ 코드 설명(핵심 라인)

dp[day] = max(dp[day], dp[day - 1]);

전날까지의 최댓값을 오늘로 전달해, “오늘 상담을 안 하는 선택”을 항상 포함시킨다.

int endDay = day + t[day] - 1;
if (endDay <= n) {
    dp[endDay + 1] = max(dp[endDay + 1], dp[day] + p[day]);
}

오늘 상담을 시작했을 때 퇴사 전 끝나는 경우만 채택하고, 종료 다음 날에 수익을 반영한다.

다른 풀이 가능성

• 뒤에서 앞으로 오는 역방향 DP(dp[i] = max(dp[i+1], p[i] + dp[i+t[i]]))도 자주 쓰는 정석 풀이이다.
• 이번 구현처럼 정방향 전파 방식은 일정표 시뮬레이션 느낌으로 읽혀 디버깅이 쉬운 장점이 있다.

오늘 정리 포인트:

• 트리에서는 “첫 방문 시 부모 확정” 패턴이 가장 단순하고 안정적이다.
• 일정 최적화 DP는 인덱스 정의를 먼저 고정하면 구현 실수가 크게 줄어든다.

내일도 유형을 섞어서 2문제 루틴을 이어갈 예정이다.