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

송진영·2022년 10월 4일
0

프로그래머스-python

목록 보기
11/22

2022 KAKAO BLIND RECRUITMENT : 양과 늑대

문제풀이

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

  1. 방문한 노드를 기록하기 위한 visited 배열 선언
  1. dfs 함수 선언
    2-1. 양의 수가 늑대보다 많을 경우, answer에 양의 수 추가하고, 적은 경우 return
    2-2. for문을 통해 갈 수 있는 노드를 확인하여 갈 수 있는 곳으로 이동하고, 방문 노드를 visited에 기록
    2-3. 위 과정을 dfs 방식으로 반복한다.
  1. 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번
profile
못하는 건 없다. 단지 그만큼 노력을 안 할 뿐이다.

0개의 댓글