주의사항- BFS의 한계가중치 그래프 적용이 불가능하다예를 들어, 미로에서 대각선 이동이 가능한 경우에는가중치가 필요하고 이를 구현하기는 불가능하다 - Dijkstra 한계 1BFS처럼 결국 완전탐색으로 동작한다 - Dijkstra 한계 2아래에서 Dijkstra를 구현하는 방식은 list를 활용한다모든 노드를 다 스캔해서 가장 최적을 고르는 방식을 채택한다그런데 우선순위 큐를 활용하면 이를 해결할 수 있다 - Dijkstra 준비물Vertex와 Cost를 합친 VertexCost 구조체를 생성한다map을 사용해서 생성하는 방법도 가능하다그리고발견목록을 저장할 discovered가장 최소거리를 저장할 best경로저장을 위한 parent가 필요하다 - Dijkstra 내부 동작BFS와 비슷한 느낌으로 동작..
주의사항 - 사용조건BFS나 DFS를 통해 그래프를 탐색하는 경우일반적으로 모든 연결관계를인접리스트 방식이나 인접행렬 방식으로 저장한 후 사용 한다그러나 이처럼 모든 관계를 메모리에 저장하지 않아도본인 기준으로 갈 수 있는 방향들만 구분이 된다면모든 연결관계를 저장할 필요는 없다 마치 미로를 탐색하는 경우에서모든 길의 값을 알 필요 없이현 위치에서의 방향만 판단하면 되는 것과 같다 BFS 길찾기 구현void Player::Bfs(){ Pos pos = _pos; // 목적지 도착하기 전에는 계속 실행 Pos dest = _board->GetExitPos(); Pos front[4] = { Pos { -1, 0}, // UP Pos { 0, -1}, // LEFT Pos { 1, 0}, // DOWN..
주의사항- "발견"이라는 개념DFS는 방문의 개념을 이용했다BFS는 발견의 개념을 이용한다 - 발견 큐DFS의 핵심은 큐를 이용하는 것이다발견한 정점들을 큐에 넣어주는 방식을 사용한다 - 발견 큐의 구조일단 큐가 비어있기 때문에시작 정점을 강제로 큐에 넣어주고 발견 여부를 true로 해주고 시작한다 이제 큐가 빌 때까지 큐를 실행하면 된다큐에 들어있는 본인이 pop 되면서, 발견한 애들을 큐에 넣으면 된다그리고 방문은 본인이 pop 되는 적절한 시점에 넣어주면 된다 - parent와 distance본인을 발견한 parent를 저장하고 싶은 경우에는큐에 push를 해주면서 발견여부를 true로 해줄 때해당 큐를 발견한 정점을 넣어주면 된다 - distanceBFS 시작 지점으로부터 거리를 알고 싶은 경우에..
주의사항- DFS의 핵심 1연결된 노드를 계속 타고 가는 것이다 - DFS의 핵심 2돌아오는 방법은 재귀함수(스택)를 이용한다 - visited 배열방문했던 곳은 제외하기 위한 visited 배열이 필요하다 - 단방향 그래프의 DFS단방향 그래프의 경우는하나의 지점에서 DFS를 진행하면 문제가 생긴다위의 그래프를 보면F를 시작 지점으로 설정하면, 그 어느 곳도 방문할 수 없다그렇기에 DFS를 모든 정점에서 실행해줘야 한다 - 트리의 DFS트리는 루트노드에서 실행하면 된다 - 양방향 그래프의 DFS양방향 그래프는 연결이 중간에 끊긴 섬과 같은 그래프가 아닌 이상은한 지점에서만 실행하면 된다 DFS 구현- 준비물struct Vertex{ // int data;};vector vertices;vector> a..
그래프의 요소정점(Vertex): 데이터를 표현하는 개념을 의미한다간선(Edge): 정점들을 연결하는 데 사용한다 그래프의 개념그래프는사물이나 추상적인 개념 간의 연결관계를 표현한다 그래프의 예시그래프는 소셜 네트워크 관계도, 지하철 노선 등매우 많이 사용된다 그래프의 종류1. 가중치 그래프정점간의 가중치가 있는 경우 사용되는 그래프이다ex. 지하철 노선도 2. 방향 그래프간선의 방향이 있는 경우 사용되는 그래프이다ex. 일반 통행이 포함된 도로망, 두 사람 사이의 호감도 그래프의 구현 방법1. 구조체 vector 방식wrapping 구조체를 이용한 방법이다void CreateGraph::CreateGraph_1(){ struct Vertex { vector edges; // int data; };..
주의사항- size와 capacity 개념이 중요하다size는 실제 사용되는 데이터의 개수를 의미하고capacity는 사용되는 데이터보다 조금 더(ex. 1.5배, 2배) 큰 크기로미리 용량을 확보해 놓은 공간의 개수를 의미한다이렇게 사용하는 이유는 배열의 크기가 변하는 경우 발생하는복사를 최소화를 하기 위해서다 - 동적배열 선언하고 reserve를 먼저 사용하는 습관실제 동적 배열을 사용하는 경우에는효율을 위해 reserve를 가장 먼저 호출해서 사용하는 것이 좋다그 이유는 데이터가 늘어나는 경우에특히, 초반에는 배열의 크기가 자주 변경되기에미리 데이터의 개수를 알고 있다면, reserve로 capacity를 지정해 주는 것이 좋다 - clear의 진실clear시 capacity는 그대로 유지된다 - ..
