흙금이네 블로그

아이디어 DFS로 각 마을을 우수 마을로 선정했을 때와 선정하지 않았을 때 가능한 최댓값을 구해 나간다. 풀이 마을의 주민 수를 리스트 P에 저장하고, 마을 간의 연결을 2차원 리스트 graph에 저장한다. dp[i][j]는 i번 마을을 루트 노드로 하여 해당 마을을 방문했을 때(j = 1)와 방문하지 않았을 때(j = 0)의 최댓값을 저장한다. 함수 dfs는 DFS로 마을을 차례로 방문하여 리스트 visited에 방문 표시 후 리프 노드부터 dp 테이블을 채워 나간다. 현재 마을을 우수 마을로 선정하지 않을 때는 연결된 마을의 우수 마을 여부와 상관없이 더 큰 최댓값을 더하고, 현재 마을을 우수 마을로 선정할 때는 연결된 마을이 우수 마을이 아닐 때의 최댓값을 더한다. 1번 마을을 루트 노드로 함수 d..