프로그래머스 양과늑대

처음 이 문제를 봤을때, 그냥 단순히 백트래킹만 하면 되는거 아닌가? 하고 백트래킹으로 문제를 풀었고, 탐색에 중복이 있다고 생각했지만 일단 풀고 안되면 다른 풀이를 봐야겠다고 생각했는데 우연히(?) 맞은 문제이다.
후에 문제풀이를 봤는데, 단순 백트래킹으로는 시간초과가 나는것이 당연하고, 중복을 제거해주어야 연산시간을 줄일 수 있엇다.

일단 내가 처음 푼 풀이는
방문 노드라면 인접한 노드에 접근한 뒤, 재귀를 돌려주는 코드이다.

from collections import defaultdict
answer = 0
def solution(info, edges):
    graph = defaultdict(list)
    for edge in edges:
        a,b = edge
        graph[a].append(b)
        graph[b].append(a)
    v = [0]*len(info)
    v[0] = 1
    tracking(graph,v,info,1,0)
    return answer

def tracking(graph,visited,info,sheep,wolf):
    global answer
    answer = max(answer,sheep)
    if sheep <= wolf:
        return
    for i in range(len(visited)):
        if visited[i]:
            for e in graph[i]:
                if not visited[e]:
                    visited[e] = 1
                    if info[e] == 1:
                        tracking(graph,visited,info,sheep,wolf+1)
                        visited[e] = 0
                    else:
                        tracking(graph,visited,info,sheep+1,wolf)
                        visited[e] = 0

하지만 이 방식은 노드의 방문에 있어서 다시 뒤로 가기 때문에 한번 갔던 경로를 다른 경로를 탐색하고 다시 올 수 있기 때문에 중복이 발생할 수 밖에 없었다.

그래서 중복을 제거해야 하는데 중복을 제거하는 방법은 비트마스킹을 사용하는 것이다.
예를 들어 방문자노드에서 0번,1번,2번 노드를 방문했다면, 111(2) 로 표현할 수 있다.
이렇게 표현하면, 111을 10진수로 변환 했을때, 단순 7이란 숫자로 모든 정보를 다 담을 수 있다는 장점이 있었다.

문제 풀이는
현재 상태를 함수의 인자로 넣고, 만약 현재상태를 방문 했었다면 return을 하였다.
현재 상태를 방문하지 않았다면, 예를 들어 1111000011(2) 라는 비트가 있을때 비트를 한칸씩 왼쪽으로 밀면서 &연산을 통해 양과 늑대의 숫자를 구하고, 해당 비트가 자식노드를 가지고 있다면, 자식 위치의 비트에 or 연산을 통해 상태에 해당 비트를 켰다.

아래 문제풀이 방식은 바킹독님의 풀이를 참고하였다.

answer = 0
n = 0
l = [-1] * 20
r = [-1] * 20
visited = [0] * (1 << 17)


def solution(info, edges):
    global n
    for edge in edges:
        a, b = edge
        if l[a] == -1:
            l[a] = b
        else:
            r[a] = b
    n = len(info)
    tracking(1, info)
    return answer


def tracking(state, info):
    global answer
    if visited[state]:
        return
    visited[state] = 1
    wolf = 0
    sheep = 0
    for i in range(n):
        if state & (1 << i):
            if info[i]:
                wolf += 1
            else:
                sheep += 1
    if wolf >= sheep:
        return
    answer = max(answer, sheep)

    for i in range(n):
        if state & (1 << i):
            if l[i] != -1:
                t = state | (1 << l[i])
                tracking(t, info)
            if r[i] != -1:
                t = state | (1 << r[i])
                tracking(t, info)