양과 늑대

날짜 : 2023. 10. 08

사용 언어 : python

 

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/92343?language=python3

 

 

 

코드

def solution(info, edges):
    visited = [False] * len(info)  # 방문처리
    res = list()
    visited[0] = True
    res.append(1)
    def dfs(sheep, wolf):
        if sheep > wolf:
            res.append(sheep)
        else:
            return
        for start, end in edges:
            if visited[start] and not visited[end]:  # 부모노드 방문 완료, 자식노드 탐색
                visited[end] = True  # 방문처리
                if info[end] == 0:  # 자식이 양
                    dfs(sheep + 1, wolf)
                else:
                    dfs(sheep, wolf + 1)
                visited[end] = False
    dfs(1, 0)  # 루트는 무조건 1
    return max(res)

 

 

풀이

- 위 문제를 해결하기 위해 고려해야 하는 요소는 총 2가지이다.

1) 양의 수가 늑대의 수보다 많은가? -> 이것은 결과를 저장할 리스트에 해당 양의 값을 넣을지 여부와, 리턴여부를 결정한다.

2) 부모 노드를 방문한 적이 있는가? -> 이진트리 형식으로 되어있기 때문에, 자식노드를 탐색하려면 필연적으로 부모노드를 방문해야 한다.

- 이를 토대로 DFS를 처리하고, 모든 노드에 대해서 뎁스마다 for문을 돌려 해당 노드의 방문여부를 체크한다.

- 만약 양이 늑대보다 많은 경우, 당시의 보유한 양의 정도를 결과 리스트에 삽입하고, 반대의 경우에는 리턴

- 이후에는 edge에 대해 전부 for문을 돌리면서 자식노드 방문 가능여부를 체크하면서 재귀를 돌린다.

 

 

알게된 점

- 위 2가지 로직을 확실하게 알지 못해 어려움을 느꼈던 문제였다.

- 일반 n * n 그래프를 통해서만 DFS, BFS를 풀다가 이런 트리 형식 탐색문제를 풀다보니 조금 생소했다.

- 그리고 모든 edge에 대해 탐색을 하는 것 또한 확실하게 떠올리지 못했던 것이 조금은 아쉬운 부분이었다.

 

 

참고 사이트

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