Coding 공부

import sys
sys.setrecursionlimit(20000)
def input():
    return sys.stdin.readline().rstrip()
def trace(cur_node,prev_check):
    visited[cur_node] = False
    flag = 0
    if not prev_check:
        if dp[cur_node][0] < dp[cur_node][1]:
            result.append(cur_node)
            flag = 1
    for next_node in graph[cur_node]:
        if visited[next_node]:
            trace(next_node,flag)
 
def dfs(node):
    visited[node] = False
    child_node = []
    for next_node in graph[node]:
        if visited[next_node]:
            child_node.append(next_node)
    if not len(child_node):
        dp[node][1] = arr[node]
 
        return
    else:
        dp[node][1] += arr[node]
        for child in child_node:
            dfs(child)
            dp[node][0] += max(dp[child][1],dp[child][0])
            dp[node][1] += dp[child][0]
 
 
 
N = int(input())
arr = [0] + list(map(int,input().split()))
 
# 1이 선택 
# 0이 선택 x
dp = [[0 for _ in range(2)] for _ in range(N+1)]
 
graph = [[] for _ in range(N+1)]
visited = [True for _ in range(N+1)]
for k in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
 
 
dfs(1)
 
print(max(dp[1]))
 
 
result = []
visited = [True for _ in range(N+1)]
trace(1,0)
result.sort()
print(*result)

어려웠던 문제였다. 트리dp를 활용해서 최적의 경우를 찾는 것은 많았지만, 그 최적을 만족하는 것을 trace를 하는 문제는 처음이라 푸는데 오래걸렸다.

dp라는 테이블을 만들고 (N+1)*2의 배열을 만들어 두었다.

여기서 1은 해당 노드를 선택했을때의 최대값

0은 해당 노드를 선택하지 않았을때의 최대값이다.

만약 리프노드이면 자신을 선택하는 조건이외에는 없을것이다.

그러므로 dp[leef_node][1] = arr[leef_node]를 넣어준다.

리프노드를 제외한 나머지 노드들은 0번 인덱스와 1번인덱스의 최대값을 구해야한다.

현재 노드를 선택했을때 즉 1번인덱스에는

현재 노드를 cur_node라고 했을때 arr[cur_node]를 더해줘야할것이다.

그리고 현재 노드를 선택했으므로, 자식노드들은 선택을 하지 못한다.

그러므로 dp[cur_node][1] += dp[child_node][0] 와 같이

자식 노드들의 선택하지않았을때의 값들을 전부 더해줘야한다.

그리고 현재 노드를 선택하지 않았을때에는

자식 노드를 선택하던지, 선택하지 않는것은 마음대로 할 수 있다.

그러므로 둘중 더 큰 값을 더해주면 된다.

이렇게 dp에 값을 누적시켜서 구하면

우리는 1번노드로 시작했기 때문에

1번노드의 dp에서 최대값을 구할 수 있다.

그러면 우리는 이 dp에서 어떤 노드들이 선택됬는지를 찾아봐야한다.

우리는 이전 노드에서 선택했는지 안했는지에 따라, 현재 노드를 선택할수 있는지 아닌지가 결정이 된다.

그래서 우리는 prev_check를 통해 문제를 해결했다. 위와 동일하게 하기 위해서 0일때에는 부모노드를 선택하지 않았다.

1일때에는 부모노드를 선택했다이다.

만약 부모노드를 선택하지 않았을때에는, 우리는 지금 있는 현재노드를 선택할지 안할지를 결정지을수 있다.

그 결정방법은 dp에 저장된 값을 비교를 해서, 우리가 선택하지 않았을때보다 선택했을때의 값이 더 크면,

그때 현재노드를 선택을 하고, flag를 1로 바꿔준다. 현재노드를 선택을 했으므로, result에 추가 시켜준다.

그리고 재귀를 통해 모든 노드들에 대해 탐색을 해주면 된다.

이 문제는 최대값을 구하는 것 뿐만 아니라, 그 경우의 수가 만들어지는 것을 찾는데 더 어려움을 겪었다.

트리 dp와 관련된 문제들을 좀 더 연습해야겠다.

import sys
 
sys.setrecursionlimit(100000)
def dfs(node):
    
    if visited[node]:
        return
    visited[node] = True
    child_nodes = []
    for next_node in graph[node]:
        if not visited[next_node]:
            child_nodes.append(next_node)
 
    if not len(child_nodes):
        dp[node][0] = town_person[node]
        return
 
    for child_node in child_nodes:
        dfs(child_node)
        dp[node][0] += dp[child_node][1]
        dp[node][1] +=  max(dp[child_node][0],dp[child_node][1])
    dp[node][0] += town_person[node]
 
 
 
 
 
N = int(input())
town_person = [0] +list(map(int,input().split()))
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
 
visited = [False]*(N+1)
dp = [[0]*2 for _ in range(N+1)]
# 0번 인덱스 : 참여를 했을때
# 1번 인덱스 : 참여를 안 했을때
dfs(1)
 
print(max(dp[1]))

# 매출하락 최소화
 
def solution(sales,links):
    N = len(sales)
    sales = [0]+sales
    tree = [[] for _ in range(N+1)]
    for parents,child in links:
        tree[parents].append(child)
    loss_sale = [[0]*2 for _ in range(N+1)]
    # loss_sale[x][0] = x번 노드가 참석하는 경우
    # loss_sale[x][1] = x번 노드가 불참석하는 경우
    def dfs(node):
        nonlocal loss_sale,tree,sales
        if not tree[node]:
            loss_sale[node][0] = sales[node]
            return
 
        for child_node in tree[node]:
            dfs(child_node)
            loss_sale[node][0] += min(loss_sale[child_node][0],loss_sale[child_node][1])
 
        
        loss_sale[node][0] += sales[node]
        atamp_loss = float('inf')
        for child_node in tree[node]:
            atamp_loss = min(loss_sale[child_node][0]-loss_sale[child_node][1],atamp_loss)
        loss_sale[node][1] = max(0,atamp_loss) + loss_sale[node][0] - sales[node]
    dfs(1)
    return min(loss_sale[1])

www.youtube.com/watch?v=FX9n1PFv2K4

BaaarkingDog 님의 풀이와 

카카오 공식블로그에 있는, tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/를 참조하여 푼 문제이다.

그러니 실질적으로, 내힘으로 푼 문제라 할순 없지만, 내가 잘 모르는 Tree-dp에 관련된 문제이고, 코드를 분석하면서, 이러한 문제 유형에 대해서 경험해보기 위해서 풀었다.

자세한 설명을 원하시는 분은 상단에 링크된 유튜브와 카카오 공식 블로그를 참조하길 바란다.

기본적인 풀이는 tree-dp에 관련된 문제였다. dp를 tree에 적용시킨 거고, dfs를 재귀방식으로 해서 푼 문제로 생각했다..

먼저 들어온 links에 대해서 부모노드에 자식노드를 추가해주는 작업을 했다.

그리고 index가 전부 1부터 시작하기 때문에 풀이의 용이함을 위해, sales 앞에 0을 추가해주었다.

이 상태에서 dfs를 통해, 매출하락 최소화를 구하는 작업을 해줬다.

loss_sale 이란 변수는 해당 노드가 워크샵에 참여유무에 따른 매출하락을 저장해놓은 변수이다.

ex ) loss_sale[x][0] 은 x번 노드가 워크샵에 참석하는 경우

      loss_sale[x][1] 은 x번 노드가 워크샵에 참석하지 않는 경우

dp는 작은단위부터 해야된다고 생각해서, 가장 끝단부터 하겠다.

1) 리프노드일 경우

  리프노드 일 경우엔, 자기자신이 참석하는 거 외에는 loss_sale을 갱신해줄만한 요소가 없다.

   loss_sale[leaf_node][0] = sales[leaf_node] 를 넣어주고 return 해주면 된다.

2) 리프노드가 아닐 경우

   리프노드가 아닐경우, 그 노드들은 팀원이면서 팀장이다. 여기서는 dfs를 들어갔을때, 팀장노드인 시점에서 들어가므로, 팀장노드라고 부르겠다.

   2-1) 팀장노드가 참석하는 경우

      > 팀장노드가 참석하는 경우에는 팀원노드들이 어떤 상태인지 상관 없기 때문에, 각 자식노드들의 참석 불참석했을          때 둘 중 최소값을 더해주면 된다.

      > 그리고 마지막으로 팀장노드의 매출 값을 저장해주면 된다.

      즉, 각 팀원노드마다  min(loss_sale[팀원노드][0],loss_sale[팀원노드][1]) 를 구해서 더해주고, 마지막에 팀장의 sales를 더해주면 된다.

   2-2) 팀장노드가 참석하지 않는 경우

       > 팀장 노드가 참석하지 않는 경우엔, 팀원 노드들 중에 한명이 무조건 참석을 해야한다. 그렇다면 매출하락폭이 최소화가 될려면 불참이었을때와 참여했을때의 loss_sale을 비교해서 그 차이가 최소값인 것을 찾아서 그 팀원노드을 선택하면 된다. 그 팀원이 불참이였다가, 참여로 전환시키는 것이기때문에 그 값을 더해주면 된다.

       > 여기서 max(0,atamp_loss)라고 해준 이유는 카카오 공식문서에서 나온 설명 마지막 부분과 부합된다.

          만약 팀원노드 A가 있다고 했을때,

          팀원노드 A가 팀장인 팀에서 최소가 되는 경우가, 팀원노드 A가 참석을 했을 때라고, 하면,

          위에서 구한, loss_sale[팀원노드 A의 부모노드][0]에 포함이 되어있을것이고, 이미 A라는 팀원이 참석한것이기

          때문에, 더해줄 필요성이 없다.

          그래서 팀원노드 A의 loss_sale은 참석했을때 loss_sale[팀원노드A][0] 보다 loss_sale[팀원노드A][1]이

           더 클 것이기 때문에 음수가 나오므로, max를 통해 0과 비교하여 음수를 방지해 주는 것이다.

        > 이렇게 참석과 불참석의 차이가 최소가 되는 노드를 선택하고 그 값에 팀장노드가 참석했을때의 값에서

           팀장노드가 참석을 안하기 때문에, 팀장노드의 매출을 빼주면 된다.

위와 같은 과정을 거친 후 CEO인 1번노드의 loss_sale의 최소값을 출력해주면 된다.

이 문제는 풀이를 보면서 풀었지만, tree와 dp에 대한 개념이 잡히지 않고서는 쉽게 풀 수 없는 문제 인것같다.

평소에도 가장 어려워하는 알고리즘이 dp와 tree이기때문에, 어려웠고, 그 2개가 합쳐진거라 더 나에게 어려움으로 느껴졌다.

이 풀이를 보면서 느낀점은 dp를 풀때에는 소분화해서 풀어야 하고, 점화식을 찾아서 동적으로 해야한다.

상반기까지 남은기간이 얼마 안남았는데,

내가 평소에 약점인 tree, dp, 플로이드, prefix_sum, 투포인터,segement tree (거의 대부분이지만) 에 대해서 더 공부해야겠다.