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

문제

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

코딩테스트 연습 - 여행경로 | 프로그래머스

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

 

입출력

tickets	return
[[ICN, JFK], [HND, IAD], [JFK, HND]]	[ICN, JFK, HND, IAD]
[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]]	[ICN, ATL, ICN, SFO, ATL, SFO]

* ticket의 원소로 주어지는 ICN, JFK 등은 공항 이름으로, 모두 문자열 형태임. ""는 편의상 생략.

입출력 예 설명

예제 #1

[ICN, JFK, HND, IAD] 순으로 방문할 수 있습니다.

예제 #2

[ICN, SFO, ATL, ICN, ATL, SFO] 순으로 방문할 수도 있지만 [ICN, ATL, ICN, SFO, ATL, SFO] 가 알파벳 순으로 앞섭니다.

 

알고리즘

import copy


def dfs(graph, start, path, length, count):
    print("\n", "---호출된 함수 정보---")
    print("DFS(",start, ")")
    path.append(start)
    print("현재까지의 path: ", path)
    print("length, count: ", length, count)

    # 티켓을 모두 사용했다면, True를 리턴한다.
    if count == length:
        print("티켓 다씀")
        return True

    try:
        # 넘겨받은 start 노드에서 갈 수 있는 다른 도시가 있는 지를 확인한다.
        graph[start]
    except:
        # 티켓을 모두 사용하지 않았는데 다른 도시로 갈 수 없다면,
        # 잘못된 경로로 들어온 것이므로 path의 마지막 원소를 pop하고 False를 리턴한다.
        print("잘못된 길로 들어옴")
        path.pop()
        return False

    # 위에 두 조건문은 재귀 호출의 정지 조건
    # 아래는, 재귀 호출하면서 할 것 정의

    # start에서 갈 수 있는 노드들을 순회한다.
    for i in range(len(graph[start])):
        dest = graph[start][i]
        print("dest: ", dest)
        count += 1

        # sub_graph 는 이미 사용한 티켓을 고려해서, 다음 후보지를 담고 있는 딕셔너리이다.
        # 이 문제 풀이의 핵심인 부분이다. 그냥 DFS만 하면, 이미 방문한 ICN 과 ATL을 계속 왕복하다 끝난다.
        # 다른 문제의 VISITED 배열과 비슷한 개념이라 생각

        # copy모듈의 deepcopy를 통해 graph를 복사한다.
        # 그냥 = 연산자를 통해 할당할 경우, sub_graph를 조작하면 graph에 영향을 미친다.
        # sub_graph = graph를 할 경우, sub_graph는 graph의 값을 갖는 것이 아니라 graph에 대한 참조를 갖기 때문

        # sub_graph[start]에는, start 노드에서 갈 수 있는 다른 노드를 담은 배열인 sub_graph[start]에서,
        # i로 선택된 노드(첫 번째 경우, ICN -> ATL이 선택되므로, ATL 노드를 말함)를 뺀 나머지를 할당한 채 
        # 재귀호출의 파라미터로 전달한다. 
        # 즉, 한번 사용한 티켓은 빼는 것.
        # [sub_graph[start]의 1번째, 2번째, ..., i-1번째 원소]  + [sub_graph[start]의 i+1번째 원소, ..., 마지막 원소]
        # sub_graph[start]가 위와 같이 바뀌어서 DFS의 파라미터로 전달된다.
        # 어떻게 바뀌는지는 콘솔창 결과 확인할 것
        sub_graph = copy.deepcopy(graph)
        sub_graph[start] = sub_graph[start][:i] + sub_graph[start][i+1:]
        print("graph[start]: ", graph[start])
        print("sub_graph[start]: ", sub_graph[start])

        # 다음 갈 수 있는 노드에 대해서 재귀 호출을 했을 때, 그 결과를 받아온다.
        # 티켓을 모두 사용했으면 True가 리턴되어 dfs_result에 저장될 것이고,
        # 잘못된 경로로 들어왔다면 False가 리턴되어 dfs_result에 저장될 것이다.
        dfs_result = dfs(sub_graph, dest, path, length, count)

        # dfs의 결과가 True라면, 그것이 정답이므로 path를 리턴한다.
        if dfs_result:
            return path

        # dfs의 결과가 False라면, 잘못된 경로로 들어온 것이므로, count를 1 감소시킨다.
        else:
            count -= 1

    # 그리고, path의 마지막 원소를 pop한다.
    popped_city = path.pop()
    print("잘못된 경로로 들어옴")
    print("pop되는 원소: ", popped_city)
    print("path: ", path, "\n")

    # return 함으로써 자신을 호출한 함수에 결과를 리턴한다.
    return


def solution(tickets):
    answer = []
    cities = []
    graph = {}

    for i in range(len(tickets)):
        for j in range(len(tickets[i])):
            if tickets[i][j] not in cities:
                cities.append(tickets[i][j])
    print("cities: ", cities)

    for i in range(len(cities)):
        graph[cities[i]] = []
        for j in range(len(tickets)):
            if cities[i] == tickets[j][0]:
                graph[cities[i]].append(tickets[j][1])
                graph[cities[i]].sort()

    print("graph: ", graph)
    print("데이터 준비끝\n")

    start = "ICN"
    path = []
    length = len(tickets)
    count = 0

    print("---DFS 재귀호출 시작---")
    answer = dfs(graph, start, path, length, count)
    return answer


tickets1 = [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"],["ATL","SFO"]]
tickets2 = [["ICN", "COO"], ["ICN", "BOO"], ["COO", "ICN"], ["BOO", "DOO"]]
print("1번답: ", solution(tickets1), "\n\n\n")
print("\n\n2번답: ", solution(tickets2))

* 위 코드에 프린트문과 주석이 너무 많아서 보기가 힘들다면, 글 맨 아래에 다 제거한 코드를 보도록 하세요.

설명

재귀적 DFS를 사용해 문제를 풀었다. 사실 내가 푼게 아니고, 좋은 풀이가 있어서, 그 코드를 낱낱이 파헤쳐보고 내가 깨달은 바를 정리한 것이다. CodeDrive라는 블로그를 운영하시는 분인데, 거의 모든 문제를 다 푸시더라. 그러나 그분께서는 너무 실력이 좋으시다보니, 다른 사람들도 본인과 같이 간단히 이해하고 풀 거라고 생각하시는 듯하다. 그래서 코드를 봐도 모르는 나같은 허접들은 따로 코드를 뜯어보며 공부해야 한다. 그래도 힌트를 주시는 것만으로도 너무너무 감사하다는 말을 올린다. 

https://codedrive.tistory.com/160

[Programmers]Lv 3. 여행경로

 

재귀 함수를 호출하기 전에, 데이터를 원하는 형태로 만들고자 한다. 딕셔너리 형태가 편하므로, 주어진 입력을 for문을 통해 정리하면 아래와 같이 나온다. 

손질한 데이터

재귀 함수를 만들기에 앞서, 해야 할 것들을 생각해보자

1. 재귀 호출의 정지 조건 만들기
2. 다음 재귀 호출에 넘길 파라미터 정하기
3. 정지 조건에 해당하지 않는 경우 재귀 함수 내부에서 할 일 정하기

재귀 함수 자습할 때 이렇게 공부했었다. 재귀 함수 활용이 서투른 분은 아래 게시물을 참조하라. 

2020/02/06 - [공부/알고리즘] - [알고리즘 자습]재귀(recursive) 함수 - N까지의 합, 거듭제곱, 구구단, 팩토리얼 등 예제- Python3

[알고리즘 자습]재귀(recursive) 함수 - N까지의 합, 거듭제곱, 구구단, 팩토리얼 등 예제- Python3

각 단계를 생각해보자. 

1. 재귀 호출의 정지 조건 만들기
   1. 그래프에서, ICN노드를 시작으로 DFS를 할건데, 우리가 원하는 경로는 티켓을 다 사용한 경로이다. 따라서, 모든 티켓이 사용되었을 때의 값을 정답으로 하고 멈출 것이다. 이는 count == length 일 때 이다. 
   2. 그런데, 간선을 따라 순회하다보면 티켓을 다 사용하지 않았는데 막다른 곳에 도착한 경우가 있다. 이러한 경우는 실패한 경우이다. 
2. 재귀 호출에 넘길 파라미터 정하기
   1. graph를 넘겨야 한다. 이 딕셔너리는 노드 간의 연결 관계를 담고 있다. 그러나 이 graph의 값을 = 연산자를 통해 temp에 가져오면, graph가 넘어오는 것이 아니라 graph에 대한 참조가 넘어온다. 이에 따라, temp를 수정할 때 graph도 수정된다. 따라서, graph를 넘겨줘야 한다. 
   2. 시작점을 넘겨야 한다. 이건 당연한 소리고, 다음 재귀 호출을 할 때는 그 다음에 갈 도시인 graph[start]의 원소들을 넘겨야 한다. 
   3. 경로을 담을 path를 넘겨준다. 만약 이상한 경로로 들어왔다면, path에 들어간 원소를 pop하면 된다.
   4. length는 ticket의 갯수이다. 뭐 꼭 넘겨줘야 되나 싶다. solution함수에서 값을 설정해놓고 하면 그 아래 함수에서 참조를 못하나? 잘 모르겠넴. 모르면 그냥 넘겨준다.
   5. count는 표를 몇 장이나 사용했는지에 대한 정보이다. 시작할 때 0을 넘겨주고, 다음 도시에 도착하면 1을 더해준다. 근데 만약 잘못된 경로로 들어왔다면, 되돌아가야하므로 count의 값을 1 뺀다. 
3. 정지 조건에 해당하지 않는 경우 재귀 함수 내부에서 할 일 정하기
   1. 정지 조건에 해당하지 않는다면, 어떤 조치를 취해주고, 다른 노드로 재귀 호출을 해야 한다. 
   2. start에서 갈 수 있는 노드들에 대해 for문을 통해 순회한다.
      1. graph에서 값을 복사해서, sub_graph에 저장한다. (copy모듈의 deepcopy() 이용 필수)
      2. sub_graph[start] = sub_graph[start][:i] + sub_graph[start][i+1:]   이 과정을 꼭 해야 한다. 즉, ICN 에서 ATL로 이동했다면, ICN에서 ATL로 가는 티켓을 이용한 것이므로, sub_graph[ICN] = [ATL, SFO]에서 ATL을 빼줘야 한다. 그러면 sub_graph[ICN] = [SFO]가 되고, 이 값을 파라미터로 넘겨준다. 
      3. 각 노드에 대해, dfs(sub_graph, graph[start][i], path, count, length)를 호출한다. 
      4. 호출한 dfs의 값을 보고, 정답을 찾았는지를 판단한다. 
         1. 만약 True라면, 정답을 찾은 것이다. 따라서, path를 리턴한다
         2. False라면, 잘못된 경로를 찾은 것이다. 따라서, count의 값을 1 감소시킨다. 
   3. for문을 빠져나왔다면, dfs_result가 False인 것이다. 따라서, 잘못된 경로를 빼줘야 하므로 path.pop()을 하고 return 한다. 

결과

아래에 콘솔창 결과를 보면, 올바른 결과를 출력한다. 

1번 답은 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"],["ATL","SFO"]] 에 대한 답이고,
2번 답은 [["ICN", "COO"], ["ICN", "BOO"], ["COO", "ICN"], ["BOO", "DOO"]] 에 대한 답이다.

위 2장의 이미지가 입력1에 대한 콘솔창 화면이다. 

아래 3장의 이미지는 입력에 대한 콘솔창 화면이다.  입력2의 경우, 경로를 잘못 찾은 경우를 고려해야 한다. 즉, ICN에서 갈 수 있는 노드를 정할 때, BOO와 COO 중 알파벳 순으로 빠른 BOO를 선택하는 게 맞다. 그러나, BOO 를 선택할 경우, ICN - BOO - DOO로 가게 되고, 더이상 갈 곳이 없다. 이러한 경우 위 알고리즘이 어떻게 대처하는 지를 살펴보자. 

잘못된 경로인 ICN - BOO - DOO 로 들어갔다가, 잘 빠져나와서 올바른 답을 출력한다. 

 

후기

게시글의 길이와, 위에 코드블럭에 들어간 프린트문, 주석의 길이만 봐도 내가 얼마나 이 문제를 어렵게 생각했는지 알 수 있다. 진짜 넘넘 어려웠다. BFS DFS를 공부를 안한것도 아니고, 재귀함수까지 공부하고 다른 문제도 풀어본 터라, 이 문제만 풀면 이제 기본빵은 치겠구나 해서 정말 내힘으로 풀고싶었는데, 3일동안 끙끙대다 못풀고 결국 다른 사람의 코드를 참고했다. 근데 봐도 이해를 못하겠더라. 그래서 이길이 내길이 맞나 싶었다. 근데 그러던 찰나, 내 친구중 하나가 그런말을 했다.

"어떤 길을 가더라도, 지금같은 역경과 고난을 마주할 것이다. 그럼 그 때, 그 시련을 이겨나가겠는가? 아니면 매 번 '이 길도 내 길이 아니구나' 하면서 포기하겠는가?"

난 그 질문에 바로 대답하지 않고, 코드를 한줄한줄 다 분석하고 어떻게 돌아가는 코드인지 프린트 다찎어보면서 이해하기 위해 노력하는 것으로 대답했다. 솔직히 아지 다 이해한건 아닌데 그래도 나중에 큰 도움이 되었음 좋겠다. 

 

아래에 프린트문과 주석 없는 코드를 첨부하니, 참고할 사람은 참고하시오

import copy
def dfs(graph, start, length, count, path):
    path.append(start)

    if count == length:
        return True
    try:
        graph[start]
    except:
        path.pop()
        return False

    for i in range(len(graph[start])):
        count += 1
        dest = graph[start][i]
        sub_graph = copy.deepcopy(graph)
        sub_graph[start] = sub_graph[start][:i] + sub_graph[start][i+1:]

        dfs_result = dfs(sub_graph, dest, length, count, path)

        if dfs_result:
            return True
        else:
            count -= 1
    path.pop()
    return False


def solution(tickets):
    cities = []
    graph = dict()
    for i in range(len(tickets)):
        for j in range(len(tickets[i])):
            if tickets[i][j] not in cities:
                cities.append(tickets[i][j])

    for i in range(len(cities)):
        graph[cities[i]] = []
        for j in range(len(tickets)):
            if cities[i] == tickets[j][0]:
                graph[cities[i]].append(tickets[j][1])
                graph[cities[i]].sort()

    start = "ICN"
    path = []
    count = 0
    cand_list = copy.deepcopy(graph[start])

    dfs(graph, start, len(tickets), count, path)
    return path