[프로그래머스]양과 늑대

[31] 양과 늑대

책 구매하기

문제 정보

• 분류: 트리
• 정답률: 33%
• 권장 시간 복잡도: O(2^N)
• 핵심 키워드: 상태 탐색, 트리, 양과 늑대, 가능 후보 집합
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/92343

문제를 읽을 때 체크할 포인트

현재 노드만 보는 DFS로는 막히기 쉽다. 이 문제는 '지금 갈 수 있는 후보 노드 집합'을 상태로 들고 다니면서, 양이 늑대보다 많은 상태만 확장해야 한다.

노드 하나를 방문했다는 사실보다 중요한 것은 지금 당장 선택할 수 있는 후보 노드가 무엇인지이다. 그래서 방문 순서만 들고 가는 탐색보다, 후보 집합을 상태로 관리하는 쪽이 문제 조건을 그대로 반영한다.

풀이 흐름

1. 간선으로 트리를 만들고 현재 방문 가능한 노드 집합을 상태에 넣는다.
2. 상태를 하나 꺼내 양 수와 늑대 수를 갱신한다.
3. 양이 늑대보다 많은 경우에만 다음 후보 상태를 큐/스택에 넣고 최대 양 수를 갱신한다.

구현할 때 놓치기 쉬운 부분

이 문제는 방문 순서만 기록하면 풀리지 않는다. 지금 시점에 갈 수 있는 후보 노드 집합이 상태라는 점을 놓치면, 중간에 잠깐 들렀다가 다른 가지로 넘어가는 경우를 표현할 수 없다.

파이썬 정답 코드

from collections import deque

def solution(info, edges):
  # 간선으로 트리를 만들고 현재 방문 가능한 노드 집합을 상태에 넣는다.
  tree = [[] for _ in range(len(info))]
  # 상태를 하나 꺼내 양 수와 늑대 수를 갱신한다.
  for parent, child in edges:
    tree[parent].append(child)

  answer = 0
  q = deque()
  q.append((0, 1, 0, tuple(tree[0])))
  visited_states = set()

  # 양이 늑대보다 많은 경우에만 다음 후보 상태를 큐/스택에 넣고 최대 양 수를 갱신한다.
  while q:
    node, sheep, wolf, candidates = q.popleft()
    state_key = (node, sheep, wolf, tuple(sorted(candidates)))
    if state_key in visited_states:
      continue
    visited_states.add(state_key)

    answer = max(answer, sheep)

    for next_node in candidates:
      next_candidates = list(candidates)
      next_candidates.remove(next_node)
      next_candidates.extend(tree[next_node])

      if info[next_node] == 0:
        q.append((next_node, sheep + 1, wolf, tuple(next_candidates)))
      elif sheep > wolf + 1:
        q.append((next_node, sheep, wolf + 1, tuple(next_candidates)))

  return answer

시간 복잡도

N은 노드 수이다.

상태가 단순 방문 순서가 아니라 선택 가능한 노드 집합까지 포함하므로 경우의 수가 부분집합 수준으로 커진다. 노드 수를 N이라 두면 최악의 상태 수를 O(2^N)으로 보는 편이 맞다.

따라서 시간 복잡도는 O(2^N)이다.

해시태그

#프로그래머스 #코딩테스트 #알고리즘 #파이썬 #자료구조 #시간복잡도 #트리 #양과늑대 #코딩테스트합격자되기 #박경록