알고리즘, 파이썬을 곁들인 (12) - 그래프 탐색

이번에는 그래프 탐색 알고리즘을 알아보자.

그래프 탐색 알고리즘은 미로 찾기 등등 여러가지 문제로 코딩 테스트에 등장하기도 한다.

바로 시작해보자.

---

우선 우리가 알아볼 그래프는 일단 이런 모양이다.

우리가 알아볼 그래프

A와 B, C, D를 각각 노드라고 부르고, 이러한 모양을 너무 대충 그렸지만 트리라고 부른다.

A는 B와 연결되어 있다.
B는 A, C, D와 연결되어 있다.
C는 B와 연결되어 있다.
D는 B와 연결되어 있다.

라고 표현할 수 있겠다.

 

 

 

자 그럼 파이썬으로 위 그래프를 표현해보자.

graph = {
    'A': ['B'],
    'B': ['A', 'C', 'D'],
    'C': ['B'],
    'D': ['B']
}

딕셔너리에 key는 각 노드를, value에는 해당 노드에 연결되어 있는 노드를 저장하는 형태이다.
이게 그래프...?

 

 

 

믿기지 않겠지만 그래프의 구현이 끝났다.
그럼 이걸로 무엇을 해볼 수 있을까.

코딩 테스트로 출제되는 미로 찾기를 간단하게 해보자.

 

 

 

A에서 시작해 C까지의 경로를 찾는 문제라고 생각해보자.
알고리즘을 작성해보자. 

1. list를 준비한다.
   이 list는 현재 노드의 위치를 저장하면서, 지나온 경로(노드들, 루트)를 기억하는 역할을 한다.
2. 시작점인 A를 list에 넣는다.
3. list의 0번째 값을 pop한다.
4. pop한 문자열의 마지막이 C인지 확인한다.
   1. C 라면, 도착한 경우이므로 경로 찾기를 종료한다.
   2. C가 아니라면, 6번으로 넘어간다.
5. pop한 문자열의 마지막 값에 연결된 노드들을 가져온다.
6. 연결된 노드들이 이전에 지나온 경로인지 확인한다.
   1. 지나온 경로가 아니라면, list에 '지나온 경로 + 연결된 노드'를 append한다.
   2. 지나온 경로라면, 무시한다.
7. list가 비었는지 확인한다.
   1. 비어있다면, A에서 C로 가는 길은 없는 것이다.
      경로 찾기를 종료한다.
   2. 비어있지 않다면, 4번으로 돌아가 반복한다.

 

 

 

바로 구현해 보자.

graph = {
    'A': ['B'],
    'B': ['A', 'C', 'D'],
    'C': ['B'],
    'D': ['B']
}

root = ['A']
found = ''

while root:
    now_root = root.pop(0)
    now_node = now_root[-1]

    if now_node == 'C':
        found = now_root
        break

    for new_node in graph[now_node]:
        if new_node not in now_root:
            root.append(f'{now_root}-{new_node}')

print(found if found else '경로가 존재하지 않습니다.')

출력 결과 :

A-B-C

훌륭하게 작동했다.

 

 

 

이제 준비했던 내용이 모두 동났다.
앞으로 작성할 알고리즘들은 공부하면서 시행착오를 겪을 예정이다.

기대도 되지만 한편으론 조금 무섭기도 하다.
그렇다고 멈춰 있을 순 없는 노릇. 나의 한계를 시험해보러 가보자.

다음 글은 브루트포스 알고리즘을 다룰 예정이다.