신촌방위본부: 지하 벙커의 비밀

이 문제는 투 스텝 문제입니다. 채점 과정과 첫 번째 실행, 두 번째 실행도 꼼꼼히 읽어 문제를 파악하시기를 바랍니다.

지난 2023년 2월 25일, 정체불명의 조직은 신촌방위본부 건물에 직접 타격을 실시하였다.

신촌방위본부 사령관은 화재로부터 많은 인원을 대피시켰지만, 건물들은 심각하게 파괴되었다.

신촌방위본부에는 $N$개의 건물과 건물들을 잇는 $N-1$개의 양방향 통로가 있으며, 임의의 서로 다른 두 건물을 통로만을 사용하여 오갈 수 있다. 또한, 임의의 건물에 연결된 통로는 최대 $3$개뿐이다. 즉, 신촌방위본부의 건물과 통로는 정점의 차수가 $3$을 넘지 않는 트리 구조를 이룬다. 또한, 각 건물은 민트색 혹은 보라색으로 칠해져 있다.

당신은 더 큰 위험에 대비하고자 하는 페인트공이다. 건물 중 정확히 한 곳에는 지하 벙커가 있고, 당신은 이 지하 벙커를 폭격 속에서도 찾아갈 수 있도록 흔적을 남기기로 결심하였다.

당신은 최대 $\mathbf{30}$번, 건물의 색깔을 민트색에서 보라색으로, 혹은 보라색에서 민트색으로 바꿀 수 있다.

2024년 2월 17일, 정체불명의 조직은 무차별 폭격을 통해 건물 간의 연결 관계와 건물의 색깔 외에는 아무것도 파악할 수 없는 폐허를 만들었다. 당신은 생존자들과 함께 지하 벙커로 이동해야 한다.

최대 $30$번의 색깔 변경으로 폭격 이후 상황에서 지하 벙커를 찾는 전략을 구상하여라.

시나리오 A

시나리오 B