그래프이론.. BFS / DFS
오늘 공부한걸 대략 정리해본다..
한달 프로젝트 할때 다른 친구들 다 하던 A*를 안해서... ㅠㅜ
안하고 그냥 누가 만든거 갖다가 쓰면 된다 하지만, 기본적인 개념은 짚고 가야 하기 때문에..........
----------
하지만 실제로 그래프 이론에서 다루는 그래프는 이렇게 생겼다..
노드(Node, 그림에서 숫자로 되어있는 것. 점)와 노드를 선(Edge)으로 이은 관계에 관한
것이다..
그림에 있는 것처럼 방향성이 없는 것이 존재하고, 방향성이 있을 수도 있다.
방향이 양방향으로 되어 있으면 '순환구조'가 되는데 무한루프에 빠질 수도 있다..
그래프 안의 노드를 탐색(Search) 하는 방법들이 BFS, DFS 다.
BFS : Breadth-First Search
DFS : Depth First Search
어느 한 지점에서, 다른 지점으로 갈 때의 방법에는
1) 한 단계씩 가본다. --- BFS
2) 모든 길을 한번씩 가본다. ----DFS
다르게 말하면. BFS는 한단계식 다음차례로 나아가며 해당 노드의 문제를 해결(어느길로 갈 것인지 결정)하기 때문에,
선입선출, Queue라고 할 수 있다. 그리고 DFS는 뒤에 있는 문제들이 하나가 해결되면 앞의 문제를 해결하는 형식이라 후입선출, Stack에 가깝다.
PPT로 1분만에 그린 그림이지만.... 예를들어,, 저 그래프(방향성이 있는) 에서 A에서 G까지 가는 길을 찾는다! 할때... 텍스트로 설명할라니 이상하지만,
BFS는 A-B-H-F-C-I-L-J-D-K-I-G..
(A에서 B로가면, A의 문제는 해결. B에서 H, F, C로 가면서 B의 문제는 해결. 다음 H, F, C가 각각 길을 찾는 형식..)
DFS는 A-B-H-I-K-H-I... /// A-B-H-I-K-L-J-K... /// A-B-C-D-G..
(A에서 B, B에서 C, F, H 중의 하나를 택하고, 우선 C로 결정한다면, C의 갈길을 끝까지 가본다. D에서는 E로 가고, G를 간다. 일단 이렇게 루트가 하나 생성되면 다시 거꾸로 갈림길이 있던 이전의 D로가서 G로 간다. )
이건 단순히 물리적 거리만 계산 할 때 최단거리를 계산할 수 있지만.. (효용)
A에서 B까지 이동하는 이동거리에 '비용'이 추가가 된다면 얘기는 달라진다.
Edge에 비용이 없다면, A에서 G까지의 최단길은 A-B-C-D-G가 당연하지만.
위와 같이 비용이 추가가 된다면, A-B-C-D-G의 길은 총 10+5+5+40, A-B-C-D-E-G는 10+5+5+10의 비용이 발생한다.
만약 마이너스의 비용이 있다면 (예를들어 지름길로 안가고 먼길로 돌아가는데 돈을 주웠다!) 얘기는 또 달라지게 된다..
같은 목적지에 도달하기까지의 여러 방법 중에서 제일 비용이 많이 들어가는 것부터 제거 해나가다보면
제일 저렴한 비용의 길을 찾을 수 있게 된다.
비용과 효용.. 어느 것을 중요하게 생각하게 생각하냐에 따라 길이 바뀐다..