양과 늑대

https://school.programmers.co.kr/learn/courses/30/lessons/92343

프로그래머스

---

try1

처음에 클래스로 노드를 만들거나 딕셔너리 형태로 graph를 만들고 풀어보려 했으나 시간효율성이 떨어지는 것 같아서 재귀함수를 이용해 풀고자 함

풀다가 코드적으로 막힌 부분은 다른 사람 코드를 참고하였음

 

※ 나의 코드

def solution(info, edges):
    answer = []
    visited = [0]
    
    # 길을 탐색하는 재귀함수
    def sw(sheep, wolf):
        if sheep > wolf:               # 양이 늑대보다 많으면 answer에 양의 개수를 넣음        
            answer.append(sheep)
        else:                          # 그렇지 않다면 해당 재귀함수를 끝냄
            return
        for edge in edges:                # 모든 노드 관계를 확인하는 for문
            parents = edge[0]             # 부모 노드
            child = edge[1]               # 자식 노드
            if parents in visited and child not in visited:    # 탐색 가능 조건 확인
                visited.append(child)             # 탐색 가능하다면 자식 노드 방문
                sw(sheep + (info[child] == 0), wolf + (info[child] == 1))  # 자식 노드 방문 결과의 양과 늑대 수로 재귀
                visited.remove(child)             # 자식 노드 탐색 초기화
    sw(1, 0)
    return max(answer)

문제풀이)

answer을 빈 리스트로 만들어주고 visited에 방문한 노드 번호를 넣기 위한 리스트로 만들어줌

visited = [0]인 이유는 처음에는 0번 노드를 방문한 상태로 시작하기 때문임

그 다음 양이 늑대보다 많게 길을 탐색하는 재귀함수 sw가 있음

sw 함수를 보면 처음 if문에서 양이 늑대보다 많다면 answer에 양의 개수를 추가한 다음 탐색을 진행하고, 그렇지않다면 재귀를 끝내서 해당 길 이상으로 더 탐색하지 않음

그 다음 for문에서 edges를 돌면서 각 edge의 부모와 자식 노드를 각각 parents와 child에 넣어줌

다음 if문에서 parents가 visited에 있고 child가 visited에 없다면 visited에 child를 추가하고 재귀적으로 sw 함수를 돔

재귀가 끝나면 visited에서 child를 제거하여 탐색을 초기화 함

이 재귀 함수가 끝나면 최종적으로 answer에 탐색 결과들의 sheep이 들어있음

max(answer)을 함으로써 양의 개수들 중 가장 큰값을 리턴해줌

 

테스트 결과) - 총합 56.75ms

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.31ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10.1MB)
테스트 4 〉	통과 (0.01ms, 10.1MB)
테스트 5 〉	통과 (0.97ms, 10.4MB)
테스트 6 〉	통과 (0.62ms, 10.3MB)
테스트 7 〉	통과 (0.18ms, 10.1MB)
테스트 8 〉	통과 (0.07ms, 10.4MB)
테스트 9 〉	통과 (0.87ms, 10MB)
테스트 10 〉	통과 (13.21ms, 10.1MB)
테스트 11 〉	통과 (0.25ms, 10.3MB)
테스트 12 〉	통과 (2.47ms, 10.2MB)
테스트 13 〉	통과 (0.04ms, 9.94MB)
테스트 14 〉	통과 (0.14ms, 10.1MB)
테스트 15 〉	통과 (1.02ms, 10.2MB)
테스트 16 〉	통과 (1.93ms, 10.2MB)
테스트 17 〉	통과 (33.99ms, 10.2MB)
테스트 18 〉	통과 (0.65ms, 10.2MB)