알고리즘 (PS)/BOJ

[백준] 1949 - 우수 마을 (Java)

2024. 11. 6. 12:08
반응형

https://www.acmicpc.net/problem/1949

 

지금까지 푼 트리 DP 문제와 같은 방법으로 풀면 된다.

다만 3번 조건이 애매하게 마음 속에 걸렸다.

뭔가 직감적으로는 내 풀이가 3번 조건을 자연스럽게 만족하는 정답을 도출할 것 같은데 확실하진 않은 느낌..

 

우선 풀이는 다음과 같다.

현재 노드를 루트로 하는 서브트리에 대해 현재 노드가 우수마을인 경우, 최적해와 우수마을이 아닌 경우 최적해를 저장하는 DP 테이블을 짜고 다음과 같이 점화식을 세운다.

 

dp[node][우수마을o] = sum( dp[child][우수마을x], ... )

dp[node][우수마을x] = sum( max(dp[child][우수마을o], dp[child][우수마을x]), ... )

 

부모 노드가 우수마을이 아닌 경우, 모든 자식에 대해 우수마을 선정 여부는 상관이 없으므로 둘 중에 최적해를 취하도록 했다.

이때 마음에 걸린 것은 혹시 부모가 우수마을이 아닐 때, 자식들도 모두 우수마을이 아닌 경우가 최적이면 어떡하지? 하는 생각이 들었다.

물론 이 경우엔 부모가 우수마을이 되는 것이 더 최적이긴 하지만, 만약 그 부모의 부모가 우수마을이라서 부모가 우수마을이 되지 않아도 된다면? 이런 생각이 들어서 긴가민가하면서 일단 구현하고 냈는데 맞았다. (prove by AC..)

 

결론적으로는 자식들이 모두 우수마을이 아닌 경우가 최적이라면 부모가 우수마을이 되는 것이 최적이라서 문제가 없다고 한다.

만약 부모의 부모가 우수마을인 경우가 최적이라서 부모가 우수마을이 아니어야 하고, 그때 자식들이 마침 모두 우수마을이 아닌 것이 최적이라면

 

그림과 같은 예시를 생각해볼 수 있다.

위 그림에서는 1억 3개를 골라서 3억을 만드는 것이 최적이다.

따라서 루트의 자식 노드가 우수마을이 아니고, 그 자식들이 모두 우수마을이 아니더라도 루트의 자식노드에 대해 계산할 때 자식들이 모두 우수마을이 아니더라도 해집합에 일단 포함시켜야 한다고 이해했다.

 

 

그 위에 최적해를 유도하는 노드가 존재하면 이때는 기존에 포함하지 않았던 1번 노드를 포함하도록 하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

    private static List<List<Integer>> graph = new ArrayList<>();
    private static int[] vertex_list;
    private static boolean[] visited;
    private static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        visited = new boolean[n];
        dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
            visited[i] = false;
        }
        vertex_list = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        for (int i = 0; i < n-1; i++) {
            String[] line = br.readLine().split(" ");
            int start = Integer.parseInt(line[0]) - 1;
            int end = Integer.parseInt(line[1]) - 1;
            graph.get(start).add(end);
            graph.get(end).add(start);
        }

        visited[0] = true;
        int ans1 = solve(0, true);
        visited[0] = true;
        int ans2 = solve(0, false);


//        for(int i = 0; i < n; i++) {
//            System.out.println(Arrays.toString(dp[i]));
//        }

        System.out.println(Math.max(ans1, ans2));
    }

    private static int solve(int node, boolean isUsu) {
        int uSuValue = isUsu ? 1 : 0;

        if (dp[node][uSuValue] != 0)
            return dp[node][uSuValue];

        int ret = 0;
        if (isUsu) {
            ret += vertex_list[node];
            for (int next_node : graph.get(node)) {
                if (!visited[next_node]) {
                    visited[next_node] = true;
                    ret += solve(next_node, false);
                }
            }
        } else {
            for (int next_node : graph.get(node)) {
                if (!visited[next_node]) {
                    visited[next_node] = true;
                    int v1 = solve(next_node, true);
                    visited[next_node] = true;
                    int v2 = solve(next_node, false);
                    ret += Math.max(v1, v2);
                }
            }
        }
        dp[node][uSuValue] = ret;
        visited[node] = false;
        return ret;
    }
}

 

그리고 파이썬을 벗어나니 파이썬이 얼마나 편했는지도 다시 깨닫는다..

입력받을 때마다 파이썬이 너무 그리워진다 ㅋㅋ

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘 (PS) > BOJ' 카테고리의 다른 글

[백준] 11437 - LCA (Python)  (0) 2024.11.08
[백준] 14442 - 벽 부수고 이동하기 2 (Java)  (0) 2024.11.07
[백준] 2533 - 사회망 서비스(SNS) (Python)  (0) 2024.11.05
[백준] 2213 - 트리의 독립집합 (Python)  (0) 2024.11.05
[백준] 1135 - 뉴스 전하기 (Java)  (0) 2024.11.04
'알고리즘 (PS)/BOJ' 카테고리의 다른 글
  • [백준] 11437 - LCA (Python)
  • [백준] 14442 - 벽 부수고 이동하기 2 (Java)
  • [백준] 2533 - 사회망 서비스(SNS) (Python)
  • [백준] 2213 - 트리의 독립집합 (Python)
에버듀
에버듀
개발은 좋은데 뭘로 개발할까
에버듀
Blog. 에버듀
에버듀
전체
오늘
어제
  • 분류 전체보기 (607)
    • 개인 프로젝트 (43)
      • [2020] 카카오톡 봇 (9)
      • [2021] 코드악보 공유APP (22)
      • [2022] 유튜브 뮤직 클론코딩 (9)
      • [2025] 고성능 에코서버 만들기 (0)
      • 간단한 프로젝트 (3)
    • 팀 프로젝트 (22)
      • [2020] 인공지능 숫자야구 (4)
      • [2022] OSAM 온라인 해커톤 (10)
      • [2024] GDSC 프로젝트 트랙 (6)
      • [2025] 큰소리 웹 페이지 (2)
    • 알고리즘 (PS) (107)
      • BOJ (101)
      • Programmers (5)
      • 알고리즘 이모저모 (1)
    • CS (329)
      • 자료구조 (19)
      • 어셈블리 (41)
      • 멀티미디어응용수학 (7)
      • 컴퓨터 구조 (29)
      • 알고리즘 분석 (4)
      • 컴퓨터 네트워크 (38)
      • 프로그래밍언어론 (15)
      • HCI 윈도우즈프로그래밍 (26)
      • 기초데이터베이스 (29)
      • 운영체제 (23)
      • 오토마타 (24)
      • 문제해결기법 (11)
      • 블록체인 (22)
      • 소프트웨어공학 (21)
      • 기계학습심화 (12)
      • 컴퓨터그래픽스와 메타버스 (8)
    • 자기계발 (38)
      • 동아리 (7)
      • 자격증 (3)
      • 코딩테스트, 대회 (8)
      • 생각 정리 (19)
      • 머니 스터디 (1)
    • WEB(BE) (5)
      • express.js (1)
      • flask (0)
      • Spring & Spring Boot (4)
    • WEB(FE) (2)
      • html, css, js (1)
      • React.js (1)
    • Tool & Language (6)
      • Edit Plus (1)
      • Git (1)
      • Python3 (2)
      • Java (2)
    • Infra (12)
      • AWS (1)
      • Oracle Cloud (8)
      • Firebase (2)
      • Network (1)
    • Android (18)
      • Java (6)
      • Flutter (12)
    • Window (2)
      • Visual Studio 없이 WPF (1)
      • MFC (1)
    • 독서 (14)
      • Inside Javascript (7)
      • Database Internals (6)
      • 한 글 후기 (1)
    • 인턴 (8)
      • 델파이 (7)
      • Oracle (1)

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.1.4
에버듀
[백준] 1949 - 우수 마을 (Java)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.