[기본_7문제_풀기/제주코딩베이스캠프] 5. 그림자 연결

5. 그림자 연결

 1) 문제: 다음 Graph를 Min, Max 값을 기준으로 Depth First Search(DFS)를 각각 진행한 뒤 나온 순서를 그대로 아스키 코드 문자로 변경하여 출력해보시오.

  - 조건: 트리문제임. DFS 알고리즘 사용할 것.

#입력
graph = {100: set([67, 66]),
         67: set([100, 82, 63]),
         66: set([100, 73, 69]),
         82: set([67, 61, 79]),
         63: set([67]),
         73: set([66]),
         69: set([66, 65, 81]),
         61: set([82]),
         79: set([82, 87, 77]),
         65: set([69, 84, 99]),
         81: set([69]),
         87: set([79, 31, 78]),
         77: set([79]),
         84: set([65]),
         99: set([65]),
         31: set([87]),
         78: set([87])}

#출력
BEAT 
CROWN

 

 2) 문제 풀이

graph = {100: set([67, 66]),
         67: set([100, 82, 63]),
         66: set([100, 73, 69]),
         82: set([67, 61, 79]),
         63: set([67]),
         73: set([66]),
         69: set([66, 65, 81]),
         61: set([82]),
         79: set([82, 87, 77]),
         65: set([69, 84, 99]),
         81: set([69]),
         87: set([79, 31, 78]),
         77: set([79]),
         84: set([65]),
         99: set([65]),
         31: set([87]),
         78: set([87])}

def MinDepthFirstSearch(graph, start):
    visited = []
    stack = [start]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            difference = graph[n] - set(visited)
            if len(difference) == 0:
                visited += stack
                break
            stack.append(min(difference))
            # print(f"visited: {visited}")
            # print(f"stack: {stack}")
    return visited

def MaxDepthFirstSearch(graph, start):
    visited = []
    stack = [start]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            difference = graph[n] - set(visited)
            if len(difference) == 0:
                visited += stack
                break
            stack.append(max(difference))
            # print(f"visited: {visited}")
            # print(f"stack: {stack}")
    return visited

print(''.join([chr(i) for i in MinDepthFirstSearch(graph, 100)[1:]]))
print(''.join([chr(i) for i in MaxDepthFirstSearch(graph, 100)[1:]]))

 

※참고자료:

2020/07/06 - [Programming/Algorithm] - [DFS, BFS/ 알고리즘] Depth First Search & Breadth First Search 알아보기

[DFS, BFS/ 알고리즘] Depth First Search & Breadth First Search 알아보기

※참고자료: 인프런 - 눈떠보니 코딩 테스트 전날! 강좌

※참고자료: 나무위키

※Copyright 사도출판 All rights reserved.

※본 게시물 속 내용을 통해 직접적으로 상업적인 목적이 없으며 게시물은 개인 공부 목적 및 지식 간단 전파목적으로 사용되었음을 명시함. 책 및 인터넷 검색을 참고자료로 하여 실습 및 학습을 한 내용을 올림. 참고한 책 및 인터넷 검색물의 저작권을 존중하므로 책 및 인터넷 저작물의 일부 또는 전부를 무단 복제 및 무단 전재 및 재배포하지 않음(일부라 함은 30%이하의 내용 중복은 불포함[30%이하는 다른 저작물로 간주]). 또한 책 또는 매체를 구매하지 않고는 정확한 내용을 알 수 없으며 개인이 따로 공부한 내용도 추가 되어 책과는 내용이 매우 상이할 수 있음.즉 본 게시물 작성자는 이 게시물을 읽는 모든 사람들이 책을 구매거나 인터넷 검색을 더하여 지식을 같이 나누었으면 좋겠음.