[프로그래머스] 양과늑대

2022 KAKAO BLIND RECRUITMENT

dfs

 

---

※ 카카오 공식 해설

 

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

 

[문제]

 

 

이진트리 문제이다.

늑대가 양보다 많은 경우를 제외하고 최대로 모을 수 있는 양의 개수를 리턴하면 된다.

 

---

[과정]

 

항상 bfs로 문제를 풀어서 dfs로직을 생각하는게 생각보다 시간이 오래걸려서 해설을 참고했다ㅎ

 

고려해야 하는 것

• 양의 수가 늑대의 수보다 많은지?
• 부모 노드를 방문한 적이 있는지?
• 자식 노드를 처음 방문하는지?

dfs()에는 양의 개수, 늑대의 개수를 매개변수로 넘기고 visited함수로 방문체크를 진행한다.

우선 양이 늑대보다 많으면 배열에 양을 저장한다.

 

이후 edge 배열을 돌면서 방문된 부모 노드가 있거나 방문되지 않은 자식노드가 있으면 자식노드를 방문처리 해주고, 조건에 따라 양 또는 늑대의 수를 업데이트 해주면서 위 과정을 반복하면 된다.

 

마지막에는 아까 저장했던 양 배열의 최댓값을 리턴하면 된다.

 

생각보다 간결한 코드로 완성이 된다.

 

---

[소스코드]

 

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)

 

---

[통과]

 

 

---

 

5/12 스터디 과제 3