2022-09-18 알고리즘 기록
🥕 문제 접근
2022 KAKAO BLIND RECRUITMENT > (L3) 양과 늑대
각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해주세요.https://school.programmers.co.kr/learn/courses/30/lessons/92343
그래프 이론인가? map으로 부모-자식 관계를 담아야 하나? 이것저것 시도 및 삽질하다가 실패 @! 결국 구글링 도움을 좀 빌렸습니다 🥺
🥕 구글링 시도
생각보다 코드가 굉장히 짧아서 한 번 놀라고 로직이 간단해서 두 번 놀랐다.
- 양의 수가 늑대의 수보다 많은가?
- 부모 노드를 방문한 적이 있는가?
- 자식 노드를 처음 방문하는가?
위 두 조건을 지켜주면 간단했다. 이제 여기에 dfs를 곁들여서 ㅎㅁㅎ
🐑 먼저 양이 늑대보다 많으면 양의 수를 결과 배열에 저장해둔다. (단, 양이 늑대보다 같거나 적으면 해당 과정을 끝낸다.)
🐺 그리고 edge 배열을 돌면서 방문된 부모 노드와 방문되지 않은 자식 노드 정보가 있으면, 1. 자식 노드에 방문 처리를 해주고 2. 양 또는 늑대 수를 업데이트 하여 같은 과정을 3. 계속 반복한다.
위 과정이 끝나면, 양의 수를 저장한 배열에서의 최댓값이 모을 수 있는 양의 최대 수가 된다.
🥕 로직을 구현한 코드
def solution(info, edges):
visited = [0] * len(info)
answer = []
def dfs(sheep, wolf):
if sheep > wolf:
answer.append(sheep)
else:
return
for p, c in edges:
if visited[p] and not visited[c]:
visited[c] = 1
if info[c] == 0:
dfs(sheep+1, wolf)
else:
dfs(sheep, wolf+1)
visited[c] = 0
# 루트 노드부터 시작
visited[0] = 1
dfs(1, 0)
return max(answer)🥕 회고
세상에 똑똑한 사람들이 많은 것 같다 👍 그래프 이론까지 생각하면서 삽질한 것이 뻘쭘할 정도로 로직과 코드가 매우 간결해서 놀랐다. BFS만 파지 말고 DFS도 좀 공부해야겠다.
