Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://www.acmicpc.net/problem/2637
2637번: 장난감조립
첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주
www.acmicpc.net
풀이
solved.ac 난이도: Gold 2
위상 정렬(Topological sort)로 해결할 수 있는 문제이다.
다른 위상정렬 문제들과는 조금 다르게 모든 케이스가 DAG가 만족하게 주어지기 때문에 부품수를 계산하는데 집중하면 된다.
이번 문제를 해결하기 위해 큐를 이용한 위상 정렬을 구현하였다.
큐를 이용한 위상 정렬에서는 노드로의 진입 차수(indegree)를 이용하는데 이 값이 0이라는 것은 해당 노드는 다른 곳으로 가는 간선(edge)이 있지만 해당 노드로 들어오는 간선은 없다는 의미이다.
중간 부품(노드)들이 다른 부품(노드)을 필요로 하는 관계(의존성)를 그래프로 표현할 때,
기본 부품의 경우 다른 부품을 필요로 하지 않기 때문에 진입하는 간선이 없다.
따라서 기본 부품은 초기 indegree가 0인 것 들이다.
기본 부품들을 큐에 넣어주고 부품의 개수만큼 아래의 계산을 진행한다.
1. 큐에서 부품하나를 꺼낸다.
2-1. 해당 부품이 기본 부품이 아니라면 해당 부품을 만드는데 필요로 하는 중간 부품들과 그 개수(num)를 찾는다.
2-2. 찾은 중간 부품이 필요로하는 기본 부품과 그 개수(base_num)
num * base_num = 중간 부품을 만들때 필요한 기본 부품의 개수이다.
따라서 중간 부품을 기본 부품의 개수로 표현 가능하다.
큐에 삽입되었다는 것은 indegree가 0, 즉 의존성이 없어졌다는 의미이므로 이미 해당 부품이 필요로 하는 부품들은 모두 기본 부품의 개수로 표현되어 있다.
3. 부품과 간선으로 연결된 다른 중간 부품(이 부품을 필요로 하는 하위 부품)과의 연결을 끊는다.
(해당 중간 부품의 indegree를 -1 줄여준다.)
4. 연결이 끊긴 부품의 indegree가 0이 된다면 큐에 삽입한다.
본인의 풀이는 (상위 부품을 필요한) 하위 부품이 (다른 부품들이 필요로 하는) 상위 부품의 필요 개수를 저장하게 하여 복잡해진 면이 있습니다.
다른 분들의 풀이에는 상위 부품이 자신을 필요로하는 하위 부품을 역으로 저장하여 더 깔끔하게 계산하게 구현하였으니
제 풀이가 이해가 되지 않으면 다른 풀이도 참고해 보시기 바랍니다.
코드
'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] No.18250 - 철도 여행 (C++, 오일러 경로) (0) | 2021.03.13 |
|---|---|
| [백준] No.3665 - 최종 순위 (C++, 위상 정렬) (0) | 2021.03.08 |
| [백준] No.2848 - 알고스팟어 (C++, 위상 정렬) (0) | 2021.03.07 |
| [백준] No.9466 - 텀 프로젝트 (C++, DFS) (0) | 2021.03.06 |
| [백준] No.13306 - 트리 (C++, 오프라인 알고리즘) (0) | 2021.03.03 |