문제
풀이
- 간선이 1개인 노드 찾기. ( 리프노드 다음 노드)
- 찾은 노드를 dp에 마스킹, 주변에 등대가 없으면 answer += 1
- lighthouse에 모든 간선이 제거되면 while 종료
계속 g 그래프를 조작하는 부분에 꽂혀서 잘못 접근했다. 간단하게 lighthouse에서 간선을 제거하고, g를 매번 초기화하는 방법으로 쉽게 풀이 가능하다.
풀이 코드
def solution(n, lighthouse):
dp = [False]*(n+1)
answer = 0
while len(lighthouse):
g = [[] for _ in range(n+1)]
for v, w in lighthouse:
g[v].append(w)
g[w].append(v)
for n in range(1, n+1):
if len(g[n]) == 1:
if dp[g[n][0]]: continue
dp[g[n][0]] = True
if not dp[n]: answer += 1
for i in range(len(lighthouse)-1, -1, -1):
if dp[lighthouse[i][0]] or dp[lighthouse[i][1]]:
del lighthouse[i]
return answer