[ 프로그래머스 / LV3 / 파이썬 Python ] 양과 늑대

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

프로그래머스

 

2022 KAKAO 블라인드 채용 코딩테스트의 기출 문제이다.
나도 당시에 테스트에 응시하며 이 문제를 접하였는데 다른 문제를 푸느라 풀 생각조차 하지 못했고 이제야 다시 풀어보게 되었다.
이번 네이버 코딩 테스트에서 크게 당한 후로 이런 것처럼 내가 지나쳐버린 문제들을 풀어봐야겠다는 생각이 들었다. 엄두도 내지 못했던 문제들을 해결하며 이후에 응시하게 될 코딩테스트에서도 자신감있게 겁먹지 않고 풀어나갈 수 있을 것 같다.

 

코드

---

from collections import defaultdict
def solution(info, edges):
    answer = 0
    childs = defaultdict(list)
    
    for a,b in edges:
        childs[a].append(b)
    
    # 양의 수, 늑대의 수, 위치
    def DFS(s,w,l,stack,visit):
        nonlocal answer
        answer = max(answer,s)
        for c in stack:
            if visit & (1 << c):
                continue
            if info[c] == 0:
                DFS(s+1,w,c,stack+childs[c],visit | (1 << c))
            elif s > w+1:
                DFS(s,w+1,c,stack+childs[c],visit | (1 << c))
    
    DFS(1,0,0,childs[0],1)
    
    return answer

 

풀이

---

문제를 접하고 카카오라는 중압감과 너무 겁먹은 나머지 엄청 어려운 방식으로 해결하려 시도했다.

위상정렬 + DP + BFS 이 세 가지 알고리즘을 합쳐서 해결하려 했다.  위상정렬을 통해 단말노드부터 탐색하는 방향을 만들어 내고 DP를 통해서 각 노드마다 도달할 때 몇 마리의 양을 얻을 수 있는지, 몇 마리의 늑대가 따라오는지를 저장하고 BFS로 루트노드부터 탐색하며 그리디하게 해결해보려고 했다.

하지만 이 세가지 알고리즘을 합쳐서 해결하기에 너무 벅찼고 예외상황이 너무 많을 것 같아서 이 방법은 아니라고 생각이 들었다. 

 

그래서 다른 방향으로 틀어보자고 생각했다.

info의 크기가 17까지밖에 올라가지 않아서 DFS 완전탐색으로도 충분할 것 같았다.

루트노드부터 시작해서 현재 위치에서 갈 수 있는 노드는 내가 방문한 노드들의 자식 노드들이다. 이 개념 하나로 언제 어디서 방향을 틀어도 상관없이 모든 노드를 탐색할 수 있었다. 또한 DFS이지만 모든 깊이까지 내려가지 않고 내가 방문할 수 있는 노드들만 탐색하며 정답을 갱신해나가서 시간복잡도 또한 별로 높지 않았다. 

방문처리는 비트마스킹을 사용해주었다. 요즘 시간복잡도를 줄이는 방향으로 코드들을 작성해나가다 보니 비트마스킹을 사용하는 것에 익숙해지고 있고 실제로 많은 효과를 보고 있다.