[DFS] leaf node부터 count 해주는 개념 익히기

DFS를 연습할 때 중요한 것은

종료 조건 (leaf node)까지 다다랐을 때부터 점차적으로 값을 누적해주는 개념이 중요하다. 
그것을 꼭 기억하자. 나 같은 경우는 DFS의 named parameter에서 정의를 해주고 leaf node에서부터 값을 가지고 이를 back tracking했을 때마다 해당된 값을 더해주는 식으로 구현하는 것이 익숙하다.

이는 MAP형태가 아니라 다음과 같은 유형에서도 반복될 수 있다. 

https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=python3

프로그래머스

 

begin = 'hit'
target = 'cog'

#words = ['hot','dot','dog','lot','log','cog']
words = ['hot','dot','dog','lot','log']

import copy

def check(src,trg) :
    cnt = 0
    for i in range(len(src)) :
        if src[i] != trg[i] :
            cnt+=1
    return cnt == 1

def solution(begin,target,words) :

    ### 애초에 target이 words에 없으면 안되겠지
    if target not in words :
        return 0 

    ## 초반에 searching할 수 있는 후보군 등록
    reps = []
    for i in range(len(words)) :
        if check(begin,words[i]) :
            reps.append(words[i])

    final_ans = 10000000

    ## 경우의 수 searching하고 가장 적은 경우로 min 값 update
    for trg in reps :
        temp = copy.deepcopy(words)
        temp.remove(trg)
        final_ans = min(final_ans,DFS(trg,temp))

    ## 이 경우는 마지막까지 도달하지 못하고 중간에 고립된 경우, 이때는 answer값이 update가 안되서 
    ## 그대로 10000000값을 가짐
    if final_ans == 10000000 :
        final_ans = 0
        
    return final_ans


def DFS(src,wrd,answer=10000000) :

    ### 종료 조건에서 cnt가 1로 시작함에 주
    if src == target :
        answer = 1
        return answer

    ### 마지막 남은 게 target이 아닌 경우, 즉 불가능 한 경우
    if src != target and len(wrd) == 1 :
        return 0

    for k in range(len(wrd)) :
        if check(src,wrd[k]) :
            temp = copy.deepcopy(wrd)
            temp.remove(wrd[k])
            answer = min(answer,DFS(wrd[k],temp)+1)

    return answer

print(solution(begin,target,words))

 

https://school.programmers.co.kr/learn/courses/30/lessons/43164?language=python3

프로그래머스

 

 

특히 이 여행 경로 문제는 처음에 단순하게 티겟을 정렬한 경우대로 단순하게 ticket에 추가하는 식으로 아래처럼 구현했다가 테케 1~2에서 에러가 발생했다. 

tickets = [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]
#tickets = [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]
#tickets = [['ICN','BKD'],['BKD','ICN']]
#tickets = [["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]

import copy

def DFS(start,ticket,answer) :
    print(ticket)

    if not ticket :
        answer.append(start)
        return answer
    
    nexts = []
    for rest in ticket :
        if rest[0] == start :
            nexts.append(rest)

    if not nexts :
        return []

    nexts.sort()

    for i, represent in enumerate(nexts) :
        #temp = copy.deepcopy(ticket)
        #temp.remove(represent)
        temp = ticket.pop(i)
        answer.append(temp[1])
        answer = DFS(represent[0][1],temp,answer)
        if answer :
            return answer

    return answer
        
def solution(tickets) :
    start = 'ICN'
    nexts = []

    for rest in tickets :
        if rest[0] == 'ICN' :
            nexts.append(rest)

    nexts.sort()
    answer = ['ICN']

    for represent in enumerate(nexts) :
        #temp = copy.deepcopy(tickets)
        #temp.remove(represent)
        tickets.remove(represent)
        answer.append(represent[1])
        answer = DFS(represent[0][1],tickets,answer)
        if answer :
            break
        tickets.insert(i,temp)
        answer.pop()

    return answer

print(solution(tickets))

 

이유를 찾아보니 아래 반례처럼

tickets = [["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]

우선적으로 알파벳 순이 가까운 것만 탐색했다가 중간에 목적지로 도달하지 못하는 예외 케이스를 생각을 못했기 때문이다. 이 경우에 대한 DFS 종료 조건이 추가로 필요했고 이 경우 다음 정렬 순의 티켓을 탐색해야 한다. 살짝 back tracking의 논리가 들어간다.

이 때 중요한 점은, 리프 노드부터 역으로 answer 배열에 하나씩 티겟을 추가하는 식으로 구현했고 마지막으로 순서를 reverse하는 식으로 구현을 하였다. 이러한 DFS 폼에 보다 더 익숙해지자