BOJ 9672 Traitor
BOJ 9672 Traitor
문제 내용
명의 사원이 근무하는 어떤 회사에서, 각 사원은 직속 상사가 0명 또는 1명 있습니다. 상사가 없는 사원이 여러 명일 수도 있습니다.
이 회사의 사원들 중 누군가가 범죄를 저질렀습니다. 용의자가 명일 때, 다음의 조건을 충족시키면서 동시에 감시할 수 있는 용의자의 수의 최댓값을 구하세요.
- 한 사원은 자신의 직속 상사나 직속 부하를 감시할 수 있습니다. 단, 감시하고자 하는 대상이 용의자가 아니면 감시하면 안 됩니다.
- 한 사원이 2명 이상의 다른 사원을 동시에 감시할 수는 없습니다.
- 한 사원이 누군가를 감시하면서 동시에 다른 누군가한테 감시당할 수는 있으나, 두 사원이 서로를 감시할 수는 없습니다.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있으며, 0 0으로 종료됩니다.
각 테스트 케이스에 대해, 첫 줄에는 과 가 주어집니다. (, )
두 번째 줄에는 각 사원의 직속 상사의 번호가 주어집니다. 각 사원은 1부터 까지의 번호가 순서대로 붙어있으며, 직속 상사가 없으면 0이 주어집니다.
세 번째 줄에는 용의자들의 번호가 주어집니다.
출력
각 테스트 케이스에 대해, 문제의 정답을 한 줄에 출력합니다.
문제 풀이
스포일러
이 문제는 다음과 같은 트리 DP로 풀 수 있습니다.
- 각 정점의 상태를 “다른 사원을 감시할 수 있는지” (a), 그리고 “다른 사원에게 감시당할 수 있는지” (b)로 나누어 총 4개의 상태를 만듭니다.
- 리프 정점에서는 그 정점이 용의자인지에 따라
10또는11에 DP값으로 0을 주고 나머지 상태는 불가능하므로-INF를 줍니다. - 리프가 아닌 정점에서의 DP값은 다음과 같이 구합니다.
- 먼저 현재 정점이 용의자라고 가정합니다.
11은 단순히 각 자식 정점들의00,01,10,11값 중 최댓값들의 합으로 구할 수 있습니다.10은 자식 중 하나를 골라 현재 정점을 감시하게 해야 합니다. 이때의 가능한 최댓값은 위의 최댓값들의 합에서 어떤 자식 정점 중 하나의 a를 1로 만드는 페널티 중 최솟값을 빼고 1을 더해서 구할 수 있습니다.01은 비슷하게 b를 1로 만드는 페널티 중 최솟값을 빼고 1을 더해서 구할 수 있습니다.- 여기까지 구하기 위해서 a를 1로 만드는 페널티의 목록과 b를 1로 만드는 페널티의 목록을 저장하였다면,
00도 다음과 같이 구할 수 있습니다.- a를 바꾸는 최소 페널티인 정점과 b를 바꾸는 최소 페널티인 정점이 서로 다르면, 둘을 모두 빼고 2를 더합니다.
- 두 정점이 서로 같으면, a에서 두 번째 정점을 선택하는 것과 b에서 두 번째 정점을 선택하는 것 중 최선을 고릅니다.
- 두 번째 정점이 존재하지 않으면
-INF입니다.
- 현재 정점이 용의자가 아닌 경우, 위에서 구한
01과11을 각각00과10에 넣고, 나머지 두 자리는-INF로 둡니다.
그리디하게 접근하면 틀리기 쉽습니다. 예를 들어 다음의 그리디 전략은 아래의 반례가 있습니다.
- 트리 DP처럼 하는데, 각 정점을 감시할 수 있는지와 감시당할 수 있는지만 넘깁니다. 감시할 수 있는 자식과 감시당할 수 있는 자식을 다르게 고를 수 있으면 2를 더하고, 그렇지 않으면 부모가 자식을 감시하는 것을 우선으로 합니다.
8 7
0 1 2 3 1 3 4 6
1 3 4 5 6 7 8이 경우 아래쪽 5개 정점 중에서 4개를 감시하는 방법이 최선인데, 그리디 전략을 사용할 경우 양쪽이 대칭적으로 올라가기 때문에 그러한 방법을 찾는 것이 불가능합니다.
Last updated on