프로그래머스 등대 (1) 썸네일형 리스트형 [프로그래머스][Swift] 등대 - Level3 프로그래머스 문제 [ 링크 ] 간단한 문제 요약n개의 등대가 있고, 등대와 등대 사이 오가는 뱃길은 n-1개 존재한다. 어느 등대에서 출발하든, 다른 모든 등대로 이동할 수 있다. 몇개의 등대만을 켜서 전력을 아끼려구 한다. 한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져있도록 등대를 켜 두어야 한다.문제 풀이처음엔 그리디하게 문제를 접근했는데 가장 많이 연결된 등대를 키지 않고도 그 주위의 등대들을 켜 두면, 최소한의 켜진 등대 개수가 구해질 수 있었습니다. (x) "한 정점에서 다른 모든 등대로 이동할 수 있다 + n개의 등대 및 뱃길은 n-1개 존재한다." 에서 이 문제는 사이클이 없는 그래프임을 알 수 있습니다. (트리)(n개의 정점 중 간선이 n-1개) dfs와 dp를 통해 특정 정점에서 등대.. 이전 1 다음
