[알고리즘] 프로그래머스 여행경로 - Python

문제 : 프로그래머스 여행경로 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

 

이 문제는 파이썬 문법을 정확히 알아야겠다고 생각하게 된 계기가 되었다. 먼저 문제를 보자마자 그래프, dfs가 떠올랐다. 

 

먼저 구현한 방법은 아래와 같다.

 

def solution(tickets):
    answer=[]
    ans=[]
    dict={}
    ticket=0
    for i in tickets:
        ticket+=1
        if i[0] in dict:
            dict[i[0]].append([i[1],0])
            dict[i[0]].sort()
        else:
            dict[i[0]]=[[i[1],0]]
    
    def dfs(loc):
        nonlocal ans
        if len(answer)==ticket+1:
            if len(ans)==0 : 
                ans = answer[:]
            
            return answer
            
        elif loc in dict:
            for i in dict[loc]:
                if i[1]==0:
                    i[1]=1
                    answer.append(i[0])
                    dfs(i[0])
                    i[1]=0
                    answer.pop()
    answer.append("ICN")
    dfs("ICN")
    return ans

 

각 변수들을 설명해보겠다.

• dict : tickets를 딕셔너리로 만든 것이다. 

{'ICN': [['ATL', 0], ['SFO', 0]], 'SFO': [['ATL', 0]], 'ATL': [['ICN', 0], ['SFO', 0]]}

 

ICN에서 출발하는 티켓은 총 2개이고, 각 티켓 리스트의 2번째 요소인 0은 해당 티켓을 사용했는지를 나타낸 것이다.

• ans : 최종 경로를 저장하는 리스트
• answer : dfs를 하면서 경로를 저장하는 리스트 

여기서 ans와 answer의 차이는 answer는 dfs를 거치면서 초기화되지만, ans는 만약 경로가 완성되었다면 다시 초기화되지 않는다.

 

이 문제에서는 ans를 초기화하지 않고, 처음 완성된 경로 그대로 할 수 있었던 이유는 먼저 dictionary를 sort해주었기 때문이다. 가장 첫 for 반복문을 보면 티켓을 하나 추가할 때마다 sort를 하는 것을 볼 수 있다. 따라서 가장 처음 방문한 경로가 알파벳 순으로 정렬된 것을 알 수 있다. 

 

dfs에서 중요한 것은 방문 여부와 answer 경로를 dfs를 수행했다가 나올 때 다시 초기화하는 것이다. 따라서 코드에 보면 

i[1]=1
answer.append(i[0])
dfs(i[0])
i[1]=0
answer.pop()

 

dfs를 방문하기 전에 i[1]을 1로 수정하여 방문 표시를 해주고, answer 배열에 경로를 추가한다. 그리고 dfs를 나온 이후에는 다시 dfs i[1]은 0으로, answer에서 경로는 삭제해준다. 이렇게 되면 문제가 dfs가 모두 완료된 이후에 answer를 보면 빈 배열이라는 것이다. 따라서 만약 경로가 완성되면 그걸 저장해둘 배열이 필요하다. 그게 바로 ans 배열인 것이다.

 

C++을 사용하다가 파이썬으로 오면서 아직 미숙한 점이 많은 것 같다. 그래서 정리를 해보았다.

 

파이썬에서는 def 함수 안에서 변수를 사용할 때, nonlocal 선언을 해야한다. 다만, 두가지 경우가 있다.

• nonlocal 선언을 하지 않아도 되는 경우 : 값을 수정만 하는 경우 (이 코드에서는 answer 배열은 수정만 하기 때문에 nonlocal 선언이 필요 없음)
• nonlocal 선언을 해야하는 경우 : 값을 재할당해주는 경우 (이 코드에서는 ans는 재할당하기 때문에 nonlocal 선언이 필요)

배열을 복사할 떄는 두 가지가 있다.

• 두 변수가 같은 배열을 가리키는 경우 : ans = answer
• 하나의 변수가 가진 배열 그대로를 복사하는 경우 : ans = answer[:]

이 코드에서는 후자를 선택했다. 전자를 선택할 경우 answer가 계속해서 초기화되는 동안 ans도 영향을 받기 때문이다.

 

def solution(tickets):
    answer=[]
    ans=[]
    dict={}
    visit={}
    ticket=0
    for i in tickets:
        ticket+=1
        if i[0] in dict:
            dict[i[0]].append([i[1],0])
            dict[i[0]].sort()
            visit[i[0]].append(0)
        else:
            dict[i[0]]=[[i[1],0]]
            visit[i[0]]=[0]
    
    def dfs(loc):
        if len(answer)==ticket+1:
            return answer
            
        elif loc in dict:
            for i in dict[loc]:
                if i[1]==0:
                    i[1]=1
                    answer.append(i[0])
                    temp=dfs(i[0])
                    if temp: return temp
                    i[1]=0
                    answer.pop()
    answer.append("ICN")
    ans = dfs("ICN")
    return ans

 

또는 ans 변수 없이 temp를 활용하여 이렇게 구하는 방법도 있을 것 같다.

 

 

dfs 구현은 금방 하지만, 자잘한 문제들이 있어서 시간이 꽤 소요되었던 문제이다..