[Python] 양과 늑대

1. 문제https://programmers.co.kr/learn/courses/30/lessons/92343

코딩테스트 연습 - 양과 늑대

2. 코드

def nextnode(now,edges):
    queue = []
    for i in edges:
        if i[0] == now:
            queue.append(i[1])
        if i[1] == now:
            queue.append(i[0])
    return queue
    
def dfs(now, sheep, wolf, info, edges, cango_list, new_visit_list):
    global max_sheep
    new_visit = new_visit_list[:]
    cango = cango_list[:]

    # 첫 방문 노드라면 0로 바꿔주고 늑대 & 양 개수 업데이트
    if new_visit[now]:
        new_visit[now] = 0
        if info[now] == 0 : sheep = sheep + 1 
        else : wolf = wolf + 1
    
        # 현재 양이 max인지 체크
        if (sheep > max_sheep) :
            max_sheep = sheep
            
    # 다 잡아먹히면 return
    if (sheep == wolf) : 
        return 0
    
    # 아니면 계속 진행해보기
    cango = cango + nextnode(now,edges)
    for i in cango:
        # 방문을 안했었던 노드 방문
        if new_visit[i]:
            max_sheep = max(max_sheep, dfs(i, sheep, wolf, info, edges, cango, new_visit))

    return max_sheep
    

def solution(info_list, edges):
    global max_sheep, info
    info = info_list
    max_sheep = 0
    new_visit = [1]*(len(info))
    cango = []
    
    dfs(0,0,0,info,edges,cango, new_visit)
    
    return max_sheep

3. 회고 

• 진짜 겁나 어려웠다. 다른 사람 풀이보고도 이해 안됐음..
• 특히 왔다갔다해서 모든 경우의 탐색을 해야 되는데, 이때 나는 방문했던 곳을 또 방문해도 된다고 생각을 해서 더 헤맸다.

키 포인트

방문했던 노드 주변의 노드는 언제든지 갈 수 있다.

 

상세 설명

일번 예시를 보면

• 왼쪽에서 양을 한마리 데리고
• 오른쪽으로 가서 양을 두마리 데리고
• 다시 왼쪽으로 가서 양을 데리러 간다.

여기서 내가 했던 실수는, 그렇다면 하나의 노드를 반복해서 지나치는 것이니 중단 (return)을 visited 로 셀수 없다고 생각한 것이다.
그래서 내가 짠 코드는 root - 왼쪽 양 - 다시 root - 다시 왼쪽 양 ... 과 같이 무한정 반복이 가능해서 recursive error가 발생했다.

그러나 핵심은, 방문했던 노드는 양/늑대 상관없이 다시 방문할 수 있다는 점이다. 즉, 방문했던 노드는 언제든지 재방문이 가능하며 방문했던 노드와 인접한 노드도 언제든지 방문이 가능하다.

따라서 나는

1. 언제든지 방문이 가능한 노드를 cango = [] 배열에 넣고
2. 새로운 노드에 방문할 때 마다 인접 노드를 cango 배열에 넣어 업데이트 하며
3. 매번 for 문으로 cango (= 방문할 수 있는 노드)를 모두 탐색했다.

그러면서 max_sheep을 업데이트 해주면 된다.

# 현재 노드와 인접한 노드를 cango 배열에 넣어줌
cango = cango + nextnode(now,edges)

# 현재 노드에서 갈 수 있는 모든 노드를 재귀로 탐색 
for i in cango:
    # 방문을 안했었던 노드 방문
    if new_visit[i]:
        max_sheep = max(max_sheep, dfs(i, sheep, wolf, info, edges, cango, new_visit))

• 이렇게 쓰면서 정리하다보니.. 방문했던 노드를 하나의 노드로 합친다고 생각하면 이해가 더 쉬울 것 같다.
  구현은 이렇게 생각하면 더 어렵겠지만..?