[programmers] 양과 늑대 (python)

2024. 7. 4. 13:07·Study/algorithm
728x90
반응형

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr


bfs와 graph를 사용하려다가 틀린 문제

dfs를 통해 최대 양의 갯수를 구하면 되었다.

이때 자식 노드를 마지막엔 방문 처리를 False로 해주어 나중에 다시 그 자식 노드를 방문할 수 있게 하는 것이 중요했다.


def solution(info, edges):
    answer = []
    visited = [False] * len(info)
    
    
    def dfs(sheeps, wolves):
        if sheeps > wolves:
            answer.append(sheeps)
        else:
            return
        
        for p, c in edges:
            # 부모는 방문하였지만 자식은 방문 안한 경우만 진행
            if visited[p] and not visited[c]:
                visited[c] = True
                if info[c] == 0:
                    dfs(sheeps + 1, wolves)
                else:
                    dfs(sheeps, wolves + 1)
                # 만약 다른 곳을 들렸다 방문 시 조건에 충족할 수 있어 false 처리
                visited[c] = False
                
    visited[0] = True
    dfs(1, 0)
    
    return max(answer)
728x90
반응형

'Study > algorithm' 카테고리의 다른 글

[programmers] 단어 변환 (python)  (0) 2024.07.05
[programmers] 부대복귀 (python)  (0) 2024.07.04
[programmers] 요격 시스템 (python)  (0) 2024.07.03
[programmers] PCCP 기출문제 3번 / 아날로그 시계 (python)  (0) 2024.07.03
[programmers] PCCP 기출문제 2번 / 석유 시추 (python)  (1) 2024.07.03
'Study/algorithm' 카테고리의 다른 글
  • [programmers] 단어 변환 (python)
  • [programmers] 부대복귀 (python)
  • [programmers] 요격 시스템 (python)
  • [programmers] PCCP 기출문제 3번 / 아날로그 시계 (python)
성장형감자
성장형감자
공부 기록
    반응형
  • 성장형감자
    단순하게
    성장형감자
  • 전체
    오늘
    어제
    • Category (65)
      • Paper review (38)
        • 2D Object detection (11)
        • 3D Object detection (20)
        • 2D Segmentation (1)
        • 2D Classification (5)
        • 3D classification (1)
      • Programming (4)
        • Python (1)
        • Linux (3)
      • Project (0)
      • Study (23)
        • algorithm (20)
        • etc. (1)
        • Radar (2)
  • 인기 글

  • 블로그 메뉴

    • 홈
  • 250x250
  • hELLO· Designed By정상우.v4.10.0
성장형감자
[programmers] 양과 늑대 (python)
상단으로

티스토리툴바