링크

양과 늑대

난이도

  • 프로그래머스 난이도 3
    • 의외로 최적화 생각 안해도 풀림
    • 실전에서도 이거 최적화 어떻게 하지 하는데 풀려서 당황함

문제요약

  • 2진트리로 연결된 노드마다 양, 늑대가 존재. 양이 늑대보다 많도록 유지하며 구할 수 있는 양은 최대 몇 마리인지.

접근

  • bfs를 이용해 양과 늑대의 갯수를 확인하면서 모든노드를 탐색
    • 단순히 양이 있는곳으로만 가지 않기

간단 알고리즘

  • bfs를 이용
    • info는 해당 노드에 양은1, 늑대는 0으로 표시된 배열
    • edges는 노드와 연결된 자식 노드 번호를 가지는 adjancy list(인접 리스트)
    • 구하려는 양의 최대 갯수 maxship=0으로 선언
    • [현위치cur, 양갯수s, 늑대갯수w, 방문한노드체크save, 이동가능한노드들nexts]형태로 queue에 들어간다.
    • 초기화
      • [0, 0, 0, [0, 0, 0, …], [] ]로 초기화하여 queue에 입력
    • 반복
      • queue 크기가 0이면 종료
      • queue에서 하나 빼서 진행 cur, s, w, save, nexts
      • save[cur]==1이면 더 진행하지 않고 queue다음거 확인
        • 현재 노드를 반문 했었다는 의미
      • 양과 늑대 확인
        • info[cur]==1이면 양을 얻었다는 의미
          • s+=1
        • 그외
          • w+=1로 늑대 증가
      • 양s과 늑대w 갯수 확인
        • s>w이면
          • s>maxship이면 maxship갱신
        • s<=w이면 더 진행하지 않고 queue다음거 확인
      • 다음 이동 가능한 nexts갱신
        • edges[cur]로 현재 노드에서 이동가능한 노드를 얻는다.
        • nexts에 추가해준다.
      • 다음 이동할 노드를 nexts로 n을 이용해 반복
        • queue에 [n, s, w, save복사, nexts복사]로 추가
    • 위의 반복을 하면서 maxship이 갱신되고 이를 정답으로 반환해준다.
  • 인접리스트 edges만들기
    • dict형식으로 생성
    • 단방향이기 때문에 edges[부모노드] = [자식 노드,….]만 구성

후기

  • bfs를 구성할 수 있으면 쉽게 해결하는 문제이다.
  • bfs, dfs등을 자주 만들었으면 바로 풀었을 문제
  • 의외로 쉬움