[코딩테스트 이론] 트리

트리

• 트리의 특성을 활용하는 분야 : 계층 구조 표현 (예, 파일 시스템, 디렉터리 구조를 트리로 구성하거나 관리)
  • 인공지능
  • 자동 완성 기능 (예 : 검색 엔진에서 자동검색어 추천 기능 - 접두사나 패턴 검색)
  • 데이터 베이스
• 트리 용어
  • 루트 노드 : 노드 중 가장 위에 있는 노드
  • 에지(간선) : 노드 사이를 이어주는 선
  • 부모 - 자식 노드 / 형제노드
  • 리프 노드 : 자식이 없는 노드
  • 차수 : 특정 노드에서 아래로 향하는 간선의 개수
• 이진트리 순회하기
  • 전위 순회 : 부모노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드
  • 중위 순회 : 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드
  • 후위 순회 : 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드
• 이진 트리 탐색 (시간 복잡도 O(logN)

1. 찾으려는 값이 현재 노드 값과 동일하면 탐색 종료, 크면 오른쪽 노드 탐색
2. 찾으려는 값이 작으면 왼쪽 노드 탐색
3. 값을 찾으면 종료
   • 배열 탐색과 비교 했을 때,  데이터 크기에 따라 하위 데이터 중 한 방향을 검색대상에서 제외하므로 검색을 빠르게 만들어줌

문제1

양과 늑대

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

프로그래머스

** 내 풀이 방법

1. 간선을 트리로 표현하기

2. 현재 위치, 양개수, 늑대개수, 방문한 노드

3. bfs로 최대 양 개수 찾기.

3-1. 노드가 늑대일 경우 개수 확인 후 방문하기

3-2. 노드가 양일 경우에는 무조건 방문하기

 

어려웠던 점

이미 동일 단계의 노드를 지났을 경우에도 방문하지 않았다면 그 노드를 방문할 수 있기 때문에 중복된 노드를 저장하는 배열 (visited)를 생각하는 것이 어려웠음. 

from collections import deque

def solution(info, edges):
    #간선을 트리로 표현
    tree = [[] for _ in range(len(info))]
    for edge in edges:
        tree[edge[0]].append(edge[1])
    ans = 0    
    
    q = deque([(0, 1, 0, set())]) #현재 위치, 양 개수, 늑대개수, 방문한 노드
    #bfs
    while q:
        n, sheep, wolf, visited = q.popleft()
        ans = max(ans, sheep)
        visited.update(tree[n]) #방문 할 노드 추가
        
        for nn in visited:
            if info[nn]: #늑대일경우
                if wolf + 1 != sheep:
                    q.append((nn, sheep, wolf+1, visited-{nn}))
            else:
                q.append((nn, sheep+1, wolf, visited-{nn}))
    
    return ans