BOJ 28028 - Custodial Cleanup

BOJ 28028 - Custodial Cleanup

그리디하게 가장 많은 키를 $1$번에서 시작해 모아보자.

이런 BFS 테크닉은 가끔 나오는데 방문할 수 있는 조건이 동적일 때, 현재 방문할 수 있는건 바로 방문하고 그렇지 않은것은 다른 pending queue에 넣어두었다가 특정 노드에서 어떤 조건이 만족되면 그 조건들에 pending 되어있는 노드들을 다시 큐에 삽입시켜주는 것이다.

$1$ 번에서 방문될 수 있는 노드들의 집합 외 노드에서 $s_i \neq f_i$ 인 경우가 있다면 불가능하다.

그렇지 않다면 다음과 같은 아이디어를 써서 검사한다.

해설 왈, 그리디 알고리즘은 동작하지 않는다고 증명되었다고 한다.

모든 키를 가졌다고 해도 $c_i \neq f_i$ 인 것들때문에 항상 모든 노드를 방문할 수 있는건 아니다.

그리고 $1$번에서 시작해서 모두 두고오는 로직을 짜는건 곤란하므로, 역으로 생각하여 첫 BFS에서 방문된 노드들에 모두 $s_i=f_i$ 로 설정하고 반대로 그것들을 모두 줏어올 수 있는지를 판별한다.

이것이 성립하는 이유는 키들을 모두 두는것과 키들을 모두 줏어오는게 반대로 행동하면 동치이기 때문이다.

다만 두 번째의 BFS에서는 조건을 조금 다르게 가려는 방에 $c_i$ 에 해당하는 키가 이미 있거나 $c_i=f_i$ 인 경우에만 가도록 한다.

왜냐면 두 번째 BFS에서는 $i$ 에 진입하기 위해 $c_i$ 가 필요한게 아니라 $i$ 에서 나오기 위해 $c_i$ 가 필요하기 때문이다.

이걸 좀 더 설명하면, $i \to j$ 로 갈 때, $c_j$를 현재 키중에 갖고있거나 $c_j=f_j$ 인지 봐야한다는건 이제 $j$ 로 가면 현재 가진 키들과 $f_j$ 의 키를 원래 과정에서 가지고 있었다는 뜻인데, 그럼 $c_j$ 가 있었어야 하므로 $j$ 를 가기 직전인 $i$ 에서 (원래 과정에선 $j$ 이후에 $i$) $c_j$ 를 가지고 있어야 하거나 $c_j=f_j$ 라서 $j$ 에서 $f_j$ 키를 쓴 다음 $i$ 로 온거거나 둘 중 하나여야 한다.