[프로그래머스] 등대 (python)

 

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/133500

프로그래머스

 

 

문제

 

 

풀이

먼저 자료구조(트리)를 파악하고 탐색(DFS)을 통해 최적해(DP)를 찾기

 

- 트리

 

• 주어진 등대들은 트리 구조를 이루고 있다. 즉, 등대들은 사이클이 없는 연결된 그래프로, 뱃길은 간선 역할을 한다.
• 각 뱃길의 양 끝 등대 중 적어도 하나는 켜져 있어야 하므로, 모든 간선(뱃길)이 커버되도록 최소 개수의 등대를 켜는 것이 목표

트리와 그래프의 차이

그래프 (Graph)

• 정의: 그래프는 **정점(노드)**과 **간선(엣지)**으로 구성된 데이터 구조입니다. 간선은 노드 간의 관계를 나타냅니다.
• 방향성: 그래프는 유향 그래프(Directed Graph)와 무향 그래프(Undirected Graph)로 나뉩니다.
  • 유향 그래프: 간선에 방향이 있어, 노드 A에서 B로 가는 간선과 B에서 A로 가는 간선이 다를 수 있습니다.
  • 무향 그래프: 간선에 방향이 없으며, 노드 A에서 B로 가는 간선과 B에서 A로 가는 간선이 동일합니다.
• 사이클: 그래프는 사이클(Cycle, 순환)을 가질 수 있습니다. 즉, 그래프 내에서 출발한 노드로 다시 돌아오는 경로가 존재할 수 있습니다.
• 연결성: 그래프는 반드시 모든 노드가 연결되어 있지 않을 수도 있습니다. 연결된 컴포넌트들로 구성될 수 있습니다.
• 특징: 일반적인 그래프는 사이클이 있을 수 있고, 방향성도 가질 수 있으며, 노드 간에 여러 경로가 존재할 수 있습니다.

트리 (Tree)

• 정의: 트리는 사이클이 없는 연결된 그래프로, 모든 노드가 하나의 루트 노드에서 출발하는 트리 구조를 이룹니다.
• 방향성: 트리는 보통 무향 그래프로 간주하지만, 트리에서 각 간선은 부모 노드와 자식 노드 간의 관계를 나타내므로, 간접적으로 방향성을 가질 수 있습니다.
• 사이클: 트리는 사이클을 허용하지 않습니다. 즉, 트리에서 노드 간에 출발한 노드로 돌아오는 경로는 존재할 수 없습니다.
• 연결성: 트리는 모든 노드가 연결되어 있습니다. 트리 내에서 어느 노드에서든 다른 노드로의 경로가 반드시 존재합니다.
• 특징: 트리는 n개의 노드를 가질 때 항상 n-1개의 간선을 가지며, 사이클이 없고, 모든 노드가 연결된 계층 구조를 가집니다.

요약

• 트리는 그래프의 한 종류로, 사이클이 없고, 모든 노드가 연결된 계층적 구조를 가진다.
• 그래프는 일반적으로 사이클을 포함할 수 있고, 트리와 달리 방향성이 있을 수 있으며, 모든 노드가 반드시 연결되어 있지 않을 수 있다.

 

이 문제의 자료구조가 트리인 이유

1. 연결성: 모든 노드가 연결되어 있어, 어느 한 노드에서 다른 모든 노드로 이동할 수 있습니다.
2. 사이클 없음: 노드들 사이에 사이클이 존재하지 않습니다. 즉, 어느 노드에서 출발해 다시 그 노드로 돌아오는 경로가 없습니다.
3. 간선 수: 트리의 경우 노드의 개수가 n일 때, 간선의 개수는 항상 n-1입니다. 이미지에서 노드가 8개이고, 간선도 7개이므로 트리의 조건을 만족합니다.

- DP

 

• 트리의 루트를 임의로 선택하고, 각 노드에서의 최소 켜야 하는 등대 개수를 계산하는 방식으로 접근
• 트리를 루트에서부터 DFS 방식으로 탐색하면서, 각 노드에 대해 두 가지 경우를 고려해야 한다.
  • 해당 노드를 켜는 경우
  • 해당 노드를 켜지 않는 경우
• 이 때, 해당 노드를 켜지 않는 경우 자식 노드 중 하나는 반드시 켜져 있어야 한다.

 

문제 풀이 전략

 

• 그래프(트리) 모델링: 주어진 입력을 바탕으로 트리를 그래프로 모델링한다. 트리의 각 노드는 등대를 나타내고, 간선은 두 등대 사이의 뱃길을 나타냄
• DFS를 사용해 트리를 순회: 트리의 임의의 노드를 루트로 선택하고, 그 노드를 기준으로 **깊이 우선 탐색(DFS)**을 사용해 트리를 순회한다. 이 과정에서 각 노드를 기준으로 그 노드를 켜는 경우와 켜지 않는 경우를 고려해 최적의 결과를 계산한다.
• DP 상태 정의: 각 노드 u에 대해 다음과 같은 두 가지 상태를 정의
  • dp[u][0]: 노드 u를 켜지 않는 경우의 최소 켜야 하는 등대 수
  • dp[u][1]: 노드 u를 켜는 경우의 최소 켜야 하는 등대 수
• DP 전이식 정의: DFS로 트리를 순회하면서 각 노드에서 DP 값을 갱신
  • dp[u][1] = 1 + sum(min(dp[v][0], dp[v][1])): 노드 u를 켜는 경우, 자식 노드 v에서는 그 노드가 켜지거나 켜지지 않을 수 있으므로 자식 노드들의 최적 해를 선택합니다.
  • dp[u][0] = sum(dp[v][1]): 노드 u를 켜지 않는 경우, 자식 노드 v는 반드시 켜져야 합니다.
• 결과 계산: DFS를 통해 루트 노드까지 계산을 마쳤다면, 루트 노드의 dp 값 중 최소값을 선택한다. 즉, min(dp[root][0], dp[root][1])이 최종 답!

 

n=int(input()) # 노드 수 입력 받기
lighthouse=eval(input()) #배열 입력 받기

# 1. 트리를 만들자
tree=[[]for _ in range(n+1)]
for i in lighthouse:
    tree[i[0]].append(i[1])
    tree[i[1]].append(i[0])
# print(tree)

# 0.Dp 테이블 초기화
dp=[[0,0] for _ in range(n+1)]
visited=[0]*(n+1)

#2. dfs로 탐색하며 비교하기

def dfs(node):
    visited[node]=1 # 방문했으니까 표시하고
    dp[node][1]=1 # dp에도 기록

    for v in tree[node]: #자식 탐색 시작
        if not visited[v]:#방문(탐색)한적 없으면
            dfs(v) # 탐색 시작
            dp[node][0]+=dp[v][1]
            dp[node][1]+=min(dp[v][0],dp[v][1])

    return min(dp[1][0],dp[1][1])

print(dfs(1))

 

 

 

 

 

코멘트

- 처음엔 어떤 방식을 활용 해야 할지부터 감이 잡히질 않아 어려웠던 문제였다. 

첫 번째로, 주어진 input값을 트리 구조로 파악 후 값을 정렬하였고, 이후 dfs를 통해 dp를 활용하여 해결하였다.

dp가 여전히 어려운데ㅠㅜ 이번주 스터디 dp문제를 연속으로 해결해보며 다시 감을 익혀야겠다.