BOJ 16583 - Boomerangs
상당히 유명한(?)문제인데, 중요한 테크닉을 배울 수 있다.
그래프를 트리로 변환하는 과정인데, 이 글 을 보면 사진이 첨부되어있다.
그래프에서 풀 수 없는 문제를 블록 컷 트리같이 다양한 테크닉으로 트리로 압축을 한다든지 더미 노드나 더미 간선을 추가 한다든지 하는 테크닉을 고려해야한다.
이 문제에서 더미 노드를 붙이는 구현은 DFS spanning tree에서 부모가 아니며 자신보다 먼저 방문된 간선들에 대해서 더미노드를 생성해주면 된다.
Comments