Python algorithm 개념 및 실습 - 미로 찾기

알고리즘이란 ?

• 어떤 일을 하기 위한 명령의 집합
• 문제 해결 방법을 추상화하여 각 절차를 논리적으로 기술해 놓은 것
• 어떤 문제를 해결하기 위한 절차나 방법

 

알고리즘 복잡도

• Complexity
  • 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한가?
• 알고리즘의 성능을 객관적으로 평가하는 기준
  • 시간복잡도(time complexity) : 실행 횟수로 판단
  • 공간복잡도(space complexity) : 기억공간과 파일 공간의 사용량
• 빅오 표기법 ( Big O Notation)
  • 알고리즘이 얼마나 빠른지 표시하는 방법
  • 입력 데이터 크기 증가할 때 알고리즘 연산 시간(횟수)의 증가 방식
  • 연산의 횟수를 비교함
  • O(n) : 계산 복잡도 
    • O : 빅 O
    • n : 연산 횟수
    • O(1) : 입력 크기 n과 계산 복잡도가 무관 할때 ex) n(n+1)/2
    • O(logn) : 입력 크기 n의 로그 값에 비례하여 증가 ex) 이분탐색
    • O(n) : 입력 크기 n에 비례하여 복잡도 증가 ex) 최댓값, 순차탐색
    • O(nlogn) : 입력 크기 n과 로그 n 값의 곱에 비례하여 복잡도 증가 ex) 병합정렬, 퀵정렬
    • O(n²) : 입력 크기 n의 제곱에 비례하여 복잡도 증가 ex) 선택정렬, 삽입정렬
    • O(n₂) : 입력 크기가 n 일 때, 2의 n 제곱 값에 비례하여 복잡도 증가 ex)하노이의 탑

 

미로 찾기 알고리즘

• 미로가 주어졌을 때 출발점에서 도착점까지 가기 위한 최단 경로를 찾는 알고리즘
• 미로의 각 위치에 알파벳으로 이름 지정
• 그래프를 이용해 작성

 

 

maze = {

    "a": ["e"],

    "b": ["c", "f"],

    "c": ["b", "d"],

    "d": ["c"],

    "e": ["a", "i"],

    "f": ["b", "g", "j"],

    "g": ["f", "h"],

    "h": ["g", "l"],

    "i": ["e", "m"],

    "j": ["f", "k", "n"],

    "k": ["j", "o"],

    "l": ["h", "p"],

    "m": ["i", "n"],

    "n": ["m", "j"],

    "o": ["k"],

    "p": ["l"],

}

def solve_maze(g, start, end):

    # 앞으로 이동해야 할 이동 경로를 큐에 저장

    queue = []

    # 큐에 추가한 꼭짓점을 집합에 저장(중복 제거)

    done = set()

    # 출발점 큐와 집합에 추가

    queue.append(start)

    done.add(start)

    # 큐에 경로가 남아 있는 동안

    while queue:

        p = queue.pop(0)

        # 큐에 저장된 이동 경로의 마지막 문자가 현재 처리해야할 꼭짓점임

        v = p[-1]

        if v == end:

            return p

        for x in g[v]:

            if x not in done:

                queue.append(p + x)

                done.add(x)

 

    return "미로 탈출 불가"

print("미로찾기 : ", solve_maze(maze, "a", "p"))