728x90 백준 트리 장인 문제 파이썬 해설 코드1 백준 트리 장인 [32340] 파이썬(Python) 코드 + 해설 1. 문제 소개세종이는 정점 N개와 간선 M개로 이루어진 단순 그래프를 가지고 있다. 그는 이 그래프에 0개 이상의 간선을 추가하여 트리로 만들려고 한다. 간선을 추가할 수 있지만 기존의 간선을 제거할 수는 없다. 간선을 추가하는 방법의 가짓수를 구하고, 그 수가 K를 넘으면 −1을 출력하고, 그렇지 않으면 정확한 가짓수를 출력하는 문제다.2. 문제 해결 방법트리의 조건을 고려해보자. 트리는 사이클이 없는 연결 그래프다. 따라서 주어진 그래프를 트리로 만들기 위해서는 다음을 만족해야 한다:사이클이 없어야 한다: 기존 그래프에 사이클이 있으면 간선만 추가해서 트리로 만들 수 없다. 간선을 제거할 수 없기 때문이다.연결 그래프여야 한다: 모든 정점이 서로 연결되어 있어야 한다.따라서 주어진 그래프에서 사.. 2024. 11. 16. 이전 1 다음 728x90
