92343. 양과 늑대

플랫폼

BOJ

분류

알고리즘

중요도

티어

링크

다시 풀어도 틀릴 것 같은 문제

Created At

2023/04/15 14:36

Updated At

2023/04/15 14:42

Writer

상태

Problem

Code

#1

Idea

풀지 못해서 블로그 풀이 참고했음

노드를 왔다갔다 해야하므로, 부모노드에서 자식노드로 파고 들어가는 일반적인 dfs, bfs 로는 해결이 안 된다.

edges 에서 [부모 노드, 자식 노드] 를 받아와서

부모노드는 방문했고, 자식노드(본인)는 방문 안 한 노드만 dfs 를 해야한다.

매 방문마다 answer 리슨트에 현재의 sheep 개수를 저장하고, 모든 dfs 가 끝날 시 max(answer) 를 출력한다.

Code

def solution(info, edges):
    visited = [0] * len(info)
    answer = []
    
    def dfs(sheep, wolf):
        if sheep > wolf:
            answer.append(sheep)
        else:
            return 
        
        for parent, child in edges:
            # 부모는 방문했고, 자식노드(본인)는 방문 안 한 노드만 dfs
            if visited[parent] and not visited[child]:
                visited[child] = 1
                if info[child] == 0:
                    dfs(sheep+1, wolf)
                else:
                    dfs(sheep, wolf+1)
                visited[child] = 0

    visited[0] = 1
    dfs(1, 0)

    return max(answer)
Python
복사

Commentary

풀이 참고

[프로그래머스 L3] 양과 늑대 (python)

2022 KAKAO BLIND RECRUITMENT > (L3) 양과 늑대각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를

https://velog.io/@thguss/프로그래머스-L3-양과-늑대-python

#2

Idea

Code

Python
복사