BOJ 1005번 ACM Craft

1005번: ACM Craft

 

특정 건물의 선행 건물의 제한이 없으며, 후행 건물 또한 제한이 없기 때문에 단순 트리로는 해결이 불가능하다. 그래프를 이용해야 하며 그래프의 노드가 1000개, 간선이 100000개 이므로 완전 탐색을 한번 돌려도 시간은 충분하다. 즉 완전 탐색을 한번 돌면서 각 노드에 소요시간을 저장해 두기만 해도 해결 가능한 정석에 가까운 문제라는 생각이 들었다.

 

처음에는 단방향 그래프와 너비 우선 탐색을 이용해 구현하였으나, 이후 포스팅을 준비하면서 내 설명 능력에 한계를 느껴 약간의 성능을 포기하고 설명과 구현이 간단한 방식을 선택했다.

 

---

문제의 건물들을 그래프의 노드로 나타낸다면 노드에는 3가지 정보가 존재한다.

 

1. 건물의 번호 (건물 번호)

2. 해당 건물의 건설 소요시간 (건설 소요시간)

3. 해당 건물과 다른 건물 간의 선/ 후행 상호작용 (화살표)

 

여기에 추가로 

4. 해당 건물을 짓기 위한 선행 건물들 중 아직 지어지지 않은 건물의 수 (선행 건물)

 

 

위와 같은 노드를 이용하여 설명을 진행한다.

---

 

모든 건물들을 벡터에 넣어서 처리하고 싶다. 하지만 문제에서는 첫 번째 건물의 최소 번호가 1 인 관계로 인덱싱에 문제가 있을 수 있다.

이 문제를 해소하기 위하여 0번 건물 (소요시간 0초, 모든 건물의 선행 건물, 필요한 선행 건물의 수 0개)을 임의로 만들어주었다. 아래는 0번 건물을 추가하여 임의로 그려본 ACS Craft의 빌드오더 그래프이다.

 

이때 몇 가지 규칙을 정하고 그 규칙 대로만 (=알고리즘) 이 문제를 해결하기로 한다.

• (규칙 A) 선행 건물의 개수가 0인 건물은 건설 소요시간을 확정한 뒤 큐에 넣는다. 
• (규칙 B) 큐 최상단의 건물의 건설 소요시간을 상호작용이 있는 건물들에 임시로 저장한다. 이때 상호작용이 있는 건물의 선행 건물의 개수를 1 감한다.
  • (규칙 B-1) 단, 임시로 저장할 때 기존의 값이 새로 넣을 값보다 크다면 생략한다. 
  • (규칙 B-2) 모든 상호작용이 있는 건물에 대한 동작이 끝나면 큐에서 제거한다.
• (규칙 C) 큐가 빌 때까지 (= 모든 건물을 순회할 때까지) 규칙 A, B를 반복한 뒤 종료한다.

 

 

위의 그래프로 한 단계씩 따라가 보자.

규칙 A에 의하여 0번 건물이 큐에 들어가며, 이후 규칙 B를 실행한다.

 

규칙 B에 의해 1~5번 건물의 선행 건물 개수가 1씩 줄어들며, 0번 건물의 소요시간은 0초이기에 시간은 변하지 않는다.

 

 

규칙 A에 의해 2번, 1번, 4번 건물이 큐에 들어가 규칙 B를 적용받게 된다.

 

 

이때 2번 건물의 소요시간인 10초가 건물 3번에 임시 저장되어야 한다.

같은 방식으로 1번 건물, 3번 건물이 진행된다.

 

이때, 3번 건물이 15 + 10 + 30 이 아닌 이유는 10초 걸리는 건물과 30초 걸리는 건물을 동시에 지으면 30초에 끝나기 때문이다.

 

이때, 정상적인 큐 라면 4번이 규칙 A를 적용받아야 하지만, 설명의 편의를 위해 잠깐 맥스웰의 도깨비를 불러서 3번 건물이 먼저 규칙 A를 적용받는 상황을 만들어 본다.

 

 

 

규칙 B-1에 의해 4번 건물은 5번 건물에 자신의 소요시간을 저장시킬 수 없다. 

 

 

완전 탐색으로 모든 건물의 건설 소요시간이 확정되었으므로 건설해야 할 건물의 번호가 입력되면 해당 건물의 소요시간을 알려주면 끝.

---

 

 

code

GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지

 

백준 기준으로 실버, 골드 난이도 문제는 공략을 올리듯 가능한 가독성 좋고 쉽게 코드를 짜야겠다.

플레티넘 이상 난이도는 언젠가 내가 다시 보거나 다이아급 분들이 보시고 조언을 해주실 수 있도록 짜야겠다.

 

정도로 생각을 정리하게 된 문제였다.