[Python/프로그래머스]여행경로_DFS_(🐶삽질_깊은복사,얕은복사)

 

 

 

 

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

코딩테스트 연습 - 여행경로

 

 

 

 

---

 

 

 

코드 : 

 

from collections import defaultdict
def solution(tickets):
    answer = []
    n = len(tickets)
    def init_graph() : 
        routes = defaultdict(list) # 디포트값이 list인 딕셔너리 
        for key, value in tickets : # 출발지를 key로 dict를 만듦
            routes[key].append(value)
        return routes
    
    def dfs(key, footprint) :
        if len(footprint) == n+1 : # 다 경유한 경우 
            return footprint
        
        for idx, country in enumerate(routes[key]) : # key에서 출발하는 항공편을 돌면서 확인
            routes[key].pop(idx)
            
            fp = footprint[:]
            fp.append(country) # 지금까지의 경로에 country추가 
            
            ret = dfs(country, fp) 
            
            if ret : return ret  # 다 경유 # 모든 티켓을 이용 완료  
            
            routes[key].insert(idx, country) # pop했던 값을 다시 그자리에 넣어준다.  # 내가 간 footprint가 틀렸을 경우 if ret에 가지 못해 여기로 온다.
            
    routes = init_graph() # 출발지를 key로한 dict를 반환
    for r in routes : # routes의 key가 r으로 
        routes[r].sort() # 경로가 2개 이상일 때 알파벳 순서가 앞서는 경로
    
    answer = dfs("ICN", ["ICN"])
    
    return answer

 

 

 

for문을 돌려 key에서 갈 수 있는 
idx와 여행지를 알아낸다.(enumerate를 이용)

 

그래서 갈 수 있는 여행지로 간후 footprint에 추가하고 계속 간다. (dfs계속 호출)

그러다가 모든 여행지로 가면 return 한다. 

 

만약 내가 간 길이 모든 여행지로 갈 수 없는 길이였다면 return 값이 없으므로 

if ret : 에 걸리지않게 되고 

그 다음줄인 routes[ke].insert(idx, country)를 통해 이 여행지 안간척을 하면된다. 

 

가능한 경로가 2개 이상일 때 알파벳 순으로 가기위해서 sort해주는 것 잊지말기-!

 

 

복습하면서 쓴 코드 : 

 

from collections import defaultdict
def solution(tickets):
    routes = defaultdict(list)
    for a,b in tickets :
        routes[a].append(b)
        
    def dfs(start, footprint) :
        if len(footprint) == len(tickets) + 1 : 
            return footprint
        for i in range(len(routes[start])) :
            val = routes[start].pop(i)
            fp = footprint[:]
            fp.append(val)
            ret = dfs(val, fp)
            if ret : return ret
            routes[start].insert(i,val)
            
    for r in routes :
        routes[r].sort()
    answer = dfs("ICN" , ["ICN"])
    return answer

 

 

 

배운 점 : 

 

1. defaultdict 

default값을 지정할 수 있는 dict이다.

default값으로 int, list등으로 정할 수 있다.

 

키에 대한 값을 지정하지 않는다면 이를 default값으로 만들어준다. 

이 문제에서는 append를 이용하려고 쓴것같다. [init_graph 부분]

 

 

 

2. insert

 

 routes[key].insert(idx, country)

에서 routes[key]는 list가 되고 그 list에서 idx자리에 country를 넣으라는 의미이다. 

 

 

 

참고 블로그 :

 

https://wwlee94.github.io/category/algorithm/bfs-dfs/travel-route/

[프로그래머스] DFS & BFS - 여행 경로 / Python

 

 

 

---

 

 

여기까지가  220628에 풀었던 풀이다. 

3개월이 지난 후 다시 풀어보았다.

 

 

근데 뭐야 무조건 맞는 코드인데 자꾸 이상했다.

 

<틀린 코드>

answer = []  
def dfs(idx,val,tickets) :
    if idx == len(tickets) :
        answer.append(val)
        return
    else :
        for i in range(len(tickets)) :
            if tickets[i][0] == val[-1] :
                val.append(tickets[i][1])
                dfs(idx+1, val,tickets)
                val.pop()
def solution(tickets):              
    dfs(0,['ICN'],tickets)
    answer.sort() 
    return answer[0]

dfs 내부에서 answer을 출력하면 아주 잘 나온다.

그런데 dfs함수가 다 끝나고 출력을 하면 나오는 건 'ICN' 뿐이다...

 

이게 머람...

 

 

 

몇 시간을 해봐도 이상태 였다. 될듯 안되는 코드 때문에 답답해 미칠 지경이었다.

그래서 나는 도움을 청했다.

 

 

학교 알고리즘 동아리(디스코드), 알고리즘 빡공방(오픈카톡), 호석님의 알고리즘 공부방 (오픈카톡)에 질문을 하였다.

정말 너무 답답했다. 

 

 

다양한 조언들이 나왔다. answer을 왜 전역변수로 했는지, pop,append가 잘못된건 아닌지 , 반복문에서 0부터 돌아서 계속 'ICN'에만 있는건 아닌지 ....등등

 

반복문에서 0부터 돈다 ? 를 듣고 깨달아 vis배열을 만들었다.

vis를 만들지않으면 위 사진과 같은 경우 계속 ICN , ATL, ICN, ATL이 반복되었다. 

 

 

시간이 지나자 고수님들이 오셔서 알려주셨다..

 

당연하지만  3 공간 모두 같은 이유를 말씀을 해주셨다.

 

 

 

 

---

 

 

 

모두 정말 감사합니다..! 

 

갓호석님

 

알고리즘 빡공방

 

교내 알고리즘 동아리 소모임

 

 

 

---

 

 

그 이후에도 확실히 이해되지 않아 구글링 해보았다.

역시 갓블락디마스크님 포스팅을 해놓으셨다. 

 

 

 

얕은 복사는 대입(=), [:] 슬라이싱, 객체.copy, copy.copy 가 있고
깊은 복사는 copy.deepcopy가

그렇답니다!!

 

 

https://blockdmask.tistory.com/576

[python] 파이썬 얕은복사, 깊은복사 (copy, deepcopy, [:], =) 총 정리

 

 

 

---

그러니까 val이라는 리스트를 함수의 인수로 보내면 얕은 복사가 되어버려서 pop하는 과정에서 빠져버린다.

그래서 마지막에 "ICN"밖에 남지 않은거다!!!

 

 

이를  막기위해서는 [:]을 이용해서 만들면된다. 

물론 이것도 얕은 복사지만 여기서는 리스트 안에 리스트가 있는 것이 아니기 때문에 사용해도 무관하다. 

 

 

vis 배열을 만들고 , [:]을 이용해서  비로소 AC를 받을 수 있었다. 

 

 

<맞은 코드>

answer = []
def solution(tickets):   
    vis = [0]*len(tickets)
    
    def dfs(idx,val,tickets) :
        if idx == len(tickets) :
            answer.append(val[:])
            return
        else :
            for i in range(len(tickets)) :
                if tickets[i][0] == val[-1] and vis[i]==0 :
                    vis[i] = 1 
                    val.append(tickets[i][1])
                    dfs(idx+1, val,tickets)
                    vis[i] = 0
                    val.pop()
                    
    dfs(0,['ICN'],tickets)
    answer.sort() 
    return answer[0]

 

리스트를 함수의 인수에 넣어서 보내면 , 이후에 그 값에 변경이 일어날 경우 그 값이 변경된다. 

그러니까 얕은 복사이지만 리스트 안에 리스트가 있는게 아니므로 [:]를 사용하면 된다. ( 이해가 안되면 블락디마스크님 블로그 다시 ㄱㄱ)

 

 

 

깊은 복사로 해도 물론 된다. (import copy 해주기 )

ans.append(copy.deepcopy(travel))

 

 

 

해결했다는 것에 행복해서 주저리 주저리 적어봤다.

이렇게 🐶고생을 했는데 설마 잊어버리지 않겠지ㅣ....

 

 

 

 

복습 : 

 

✅ 20220620

✅ 20220623

✅ 20220624

✅ 20220625

✅ 20220626

✅ 20220628

🐾 20220922

🐾 20220924