developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 백준파이썬풀이
  • c++디자인패턴
  • ARIMA모형
  • 삼성코테기출
  • 통계분석
  • BOJ파이썬풀이
  • 삼성코테자바꿀팁
  • MA모형
  • 카카오코테
  • c++ 빌더 패턴
  • 시계열
  • 삼성코테구현풀이
  • 코테파이썬
  • 삼성코테자바준비
  • 삼성코테파이썬풀이
  • 카카오코테java풀이
  • 삼성코테자바풀이
  • SW역량테스트파이썬풀이
  • 삼성코테준비
  • Arima
  • 삼성코테기출자바풀이
  • SW역량테스트파이썬
  • 시계열분석
  • AR모형
  • 데이터분석
  • 삼성코테파이썬준비
  • 삼성코테구현문제추천
  • 통계학
  • 운영체제인터럽트
  • 삼성코테파이썬

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 우수 마을 1949번 (JAVA, Python)

2022. 5. 11. 21:24

❓ 문제 - 백준 우수 마을 1949번 - JAVA, Python 풀이법

 

출처 

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

 

1949번: 우수 마을

N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며,

www.acmicpc.net

 

 

📝 문제해결법

1. 이 문제는 DFS + DP, Tree DP로 해결했다.

 

[문제의 조건] 

1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.

2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을 모두 '우수 마을'로 선정할 수 없다. 즉 '우수 마을' 끼리는 서로 인접해 있을 수 없다.

3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

  • dp[마을 번호][우수마을이 아닐 때=0], dp[마을 번호][우수 마을일 때 = 1]로 두고 dfs를 돌리면서 dp에 우수 마을 일때, 우수 마을이 아닐 때의 우수마을의 주민수의 최대값을 갱신한다.
  • 3번은 딱히 고려할 필요가 없다.
  • 문제에서 조건을 확인하면 우수마을끼리는 인접하면 안된다. 
  • 따라서 현재 우수 마을(1)이라면, 인접한 곳은 우수 마을이 아닌(0) 상태이다.
  • 그리고 현재 우수 마을이 아니라면(0), 인접한 곳은 우수 마을(1) 이거나 우수 마을이(0)이 아닌 상태이다.
  • 위의 상태를 고려해서 dp값을 갱신한다. 

2. 느낀점

  • 처음에 다익스트라인줄 알고 접근했다가,, 문제가 이해가 안갔었다.
  • 코테를 볼 때마다 다익스트라와 DFS + DP OR 트리 DP를 헷갈렸는데 이런 문제를 풀어보니 약간은 감이 온 것 같다.
  • 더 익숙해지게 다양한 문제를 풀어봐야겠다.

 

💻 소스코드 (JAVA)

// BOJ - 우수 마을(1949번)
// Tree DP


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main_1949 {
	public static int n;
	public static int[] people;
	public static int[][] dp;
	public static boolean[] visited;
	public static ArrayList<ArrayList<Integer>> graph;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		n = Integer.parseInt(br.readLine());
		people = new int[n+1];
		visited = new boolean[n+1];
		graph = new ArrayList<>();

		graph.add(new ArrayList<>());
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0;i<n;i++) {
			people[i+1] = Integer.parseInt(st.nextToken());
			graph.add(new ArrayList<>());
		}

		for(int i=0;i<n-1;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
		}

		dp = new int[n+1][2];
		dfs(1);
		System.out.println(Math.max(dp[1][0], dp[1][1]));
	}

	public static void dfs(int x) {
		visited[x] = true;
		dp[x][1] = people[x];
		for(Integer i:graph.get(x)) {
			if(!visited[i]) {
				dfs(i);
				dp[x][0] += Math.max(dp[i][0], dp[i][1]);
				dp[x][1] += dp[i][0];
			}
		}
	}

}

 

💻 소스코드 (Python)

# BOJ - 우수 마을
# 트리 DP

import sys
sys.setrecursionlimit(20000)
input = sys.stdin.readline

n = int(input())
people = [0] + list(map(int, input().split()))
graph = [[] for i in range(n+1)]
dp = [[0, 0] for i in range(n+1)]
visited = [False for i in range(n+1)]


for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(x):
    visited[x] = True
    dp[x][1] = people[x]
    for i in graph[x]:
        if not visited[i]:
            dfs(i)
            dp[x][0] += max(dp[i][0], dp[i][1])
            dp[x][1] += dp[i][0]

dfs(1)

print(max(dp[1][0], dp[1][1]))

 

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 샘터 18513번 (JAVA)  (0) 2022.05.22
BOJ - 대기업 승범이네 17831번 (JAVA, Python)  (0) 2022.05.16
2021 KAKAO BLIND RECRUITMENT - 카드 짝 맞추기(JAVA)  (0) 2022.05.07
BOJ - 온풍기 안녕! 23289번 (JAVA)  (0) 2022.04.30
BOJ - 마법사 상어와 블리자드 21611번 (JAVA)  (0) 2022.04.30
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 샘터 18513번 (JAVA)
    • BOJ - 대기업 승범이네 17831번 (JAVA, Python)
    • 2021 KAKAO BLIND RECRUITMENT - 카드 짝 맞추기(JAVA)
    • BOJ - 온풍기 안녕! 23289번 (JAVA)
    developer-ellen
    developer-ellen

    티스토리툴바