전공/프로그래머스
양과 늑대
yha97
2023. 10. 8. 10:43
날짜 : 2023. 10. 08
사용 언어 : python
문제
코드
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