31477

[BOJ/백준] 31477 - 양갈래 구하기

31477번: 양갈래 구하기 다음 그림에서 1과 2를 연결하는 덩굴, 3과 6을 연결하는 덩굴, 3과 7을 연결하는 덩굴을 자르면 총 3+1+2로 6의 힘이 최솟값이 된다. www.acmicpc.net N개의 방이 존재하고 N-1개의 각 방을 잇는 덩굴이 존재하며 각 방끼리 무조건 이동 가능 = 사이클이 생길 수 없는 구조 DFS를 통한 최소 두께를 갱신하여 합 제목 양갈래 구하기 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 평화로운 양갈래의 마을에 위기가 닥쳐왔다! 덩굴에 독이 퍼져 양갈래가 있는 곳으로 옮겨지고 있다! 독은 양갈래의 방을 제외하고, 정확히 한 개의 덩굴로 연결된 방에서부터 옮겨진다. 모든 방의 쌍 사이에는 1개 이상의 덩굴을 지나는 유일한 경로가 존재하며, 덩굴은 총..