[프로그래머스] 불량 사용자(DFS)

 

https://programmers.co.kr/learn/courses/30/lessons/64064

코딩테스트 연습 - 불량 사용자

 

DFS를 활용하는 문제입니다. 

 

우선 문제부터 요약하면, 

다음과 같이 제재된 아이디와 유저의 아이디가 들어오면, 유저의 아이디로 제재된 아이디를 몇가지 조합으로 구성할 수 있는가에 관한 문제입니다. 자세한 내용은 위의 링크를 읽어보는 것이 정확합니다. 

 

간단한 예시 하나만 설명하면, 가장 첫번째의 예시는 ["fr*d*", "abc1**"] 이렇게 밴을 당하기 때문에 구성할 수 있는 조합은 

[frodo, abc123], [fradi, abc123] 이렇게 두가지가 있습니다. 두번째의 경우 *rodo가 두개 있으므로 주의해야합니다. 두번째 예시에서는 [frodo, crodo, abc123], [frodo, crodo, frodoc] 이렇게 두가지가 가능합니다. 나중에 문제를 풀 때, 중복된 카운팅을 하지 않도록 조심해야함을 알 수 있습니다. 

 

즉, solution(user_id, banned_id)에 

user_id : 응모자 아이디를 담은 배열

banned_id : 불량 사용자 아이디를 담은 배열

가 input으로 주어질 때,

 

실제 제재를 당하는 조합이 몇가지가 있는지를 return하여야합니다. 

 

<Solution>

아이디어를 간단하게 설명하면, 우선 banned_id를 기반으로 각각에 어떤 user_id가 mapping이 되는지 찾습니다. 

위 그림에서 두번째 예시인

solution(["frodo", "fradi", "crodo", "abc123", "frodoc"], ["*rodo", "*rodo", "******"])

의 상황을 예시로 설명해보겠습니다. 

*rodo가 두개 있으므로, dictionary와 같은 자료구조는 사용하지 않도록 해야합니다. 그러면 결과가 다음과 같이 나오게됩니다.

[['*rodo', ['frodo', 'crodo']], ['*rodo', ['frodo', 'crodo']], ['******', ['abc123', 'frodoc']]]

그러면 이제 DFS를 할 차례입니다. (가지치기도 함께합니다)

위의 그림을 봅시다. step 0 으로 첫번째 *rodo에 대한 조사를 합니다. frodo, crodo를 각각 stack에 넣습니다. 

pop을 하면서 만약 이미 탐색한 id가 path안에 있다면 append를 하지 않는 형식으로 가지치기를 합니다. 

이렇게 하면서 step2까지 모두 진행된 경우들을 임시로 저장해줍니다.

 

여기에서 바로 counter와 같이 숫자를 올려버리면, frodo->crodo->abc123 인경우와 crodo->frodo->abc123인 경우 같이 count되기 때문에 중복을 마지막에 set과 hashable인 tuple자료구조로 변경하여 제거해주어야합니다. 

실제로

update time path :
[['crodo', 'frodo', 'frodoc'], 2]
update time path :
[['crodo', 'frodo', 'abc123'], 2]
update time path :
[['frodo', 'crodo', 'frodoc'], 2]
update time path :
[['frodo', 'crodo', 'abc123'], 2]

실제로 출력을 해서 확인해보면, 다음과 같이 4가지가 counting되는데 이중에선 같은 것들이 존재함을 알 수 있습니다. 

 

실제 구현은 아래와 같습니다.

def solution(user_id, banned_id):
    new_list = []
    for id in banned_id:
        new_list.append([id,[]])
    
    for index, banned_id_ in enumerate(banned_id):
        for user_id_ in user_id:
            flag = 1
            for i in range(len(banned_id_)):
                if len(banned_id_) != len(user_id_):
                    flag = 0
                    break
                if banned_id_[i] == '*':
                    continue
                else:
                    if banned_id_[i] == user_id_[i]:
                        continue
                    else:
                        flag = 0
                        break
            if flag == 1:
                new_list[index][1].append(user_id_)
            else:
                continue
    path_list = []
    for element in new_list[0][1]:
        path_list.append([[element],0])
    
    total_path = []
    # dfs with pruning
    while path_list:
        # print(f'pathlist = {path_list}')
        temp_path = path_list.pop()
        if temp_path[1] == len(banned_id)-1:
            #print(f'update time path :\n{temp_path}')
            temp_path[0].sort()
            total_path.append(tuple(temp_path[0]))
            continue
        # print(f'new_list[temp_path[1]+1][1] = {new_list[temp_path[1]+1][1]}')
        for element in new_list[temp_path[1]+1][1]:
            if element not in temp_path[0]:
                append_list = temp_path[0][:]
                append_list.append(element)
                # print(f'temp_path[0][:] = {temp_path[0][:]}')
                # print(f'append_list = {append_list}')
                path_list.append([append_list,temp_path[1]+1])
    
    return len(set(total_path))