[Python] 2022 KAKAO BLIND RECRUITMENT : 양과 늑대

2022 KAKAO BLIND RECRUITMENT : 양과 늑대

문제풀이

이 문제는 dfs를 통해 양이 가장 많은 경로가 무엇인지 알아내야 한다.

1. 방문한 노드를 기록하기 위한 visited 배열 선언

2. dfs 함수 선언
   2-1. 양의 수가 늑대보다 많을 경우, answer에 양의 수 추가하고, 적은 경우 return
   2-2. for문을 통해 갈 수 있는 노드를 확인하여 갈 수 있는 곳으로 이동하고, 방문 노드를 visited에 기록
   2-3. 위 과정을 dfs 방식으로 반복한다.

3. answer 중 가장 높은 값을 return 해준다.

답

def solution(info, edges):
    visited = [0] * (len(info)) # 문제 풀이 1번
    visited[0] = 1
    answer = []
# 문제 풀이 2번
    def dfs(sheep, wolf):
# 문제 풀이 2-1번
        if sheep > wolf: 
            answer.append(sheep)
        else:
            return
# 문제 풀이 2-2번
        for i in range(len(edges)):
            parent = edges[i][0]
            child = edges[i][1]
            isWolf = info[child]

            if visited[parent] and not visited[child]:
                visited[child] = 1
                dfs(sheep+(isWolf==0), wolf+(isWolf==1)) # 문제 풀이 2-3번
                visited[child] = 0
    dfs(1,0)
    return max(answer) # 문제 풀이 3번