백트래킹, 그래프

백트래킹

• 백트래킹
• 퇴각검색이라는 뜻으로, 모든 조합을 시도해서 해를 찾는다.
• 해를 얻을 때까지 모든 경우를 시도
• 각 가능성은 트리로 생각할 수 있으며, 가지 중 해결책이 있다.
• 가지를 하나 선택하면 새로운 트리가 생성된다.
• 가지치기를 통해 필요없는 가지를 건너뛰며 탐색한다.
• 완전탐색을 통해 문제를 해결할 경우, 해답이 될 가능성이 전혀 없는 노드의 후손 노드들도 모두 검색해야 하므로 비효율적
• 백트래킹은 어떤 노드의 유망성을 검사한 후, 유망하지 않으면 부모로 돌아가 탐색을 건너뛴다.
  • 유망: 어떤 노드를 방문했을 때 그 노드를 포함한 경로가 해답이 될 수 있는 경우
  • 가지치기: 더 이상 해당 경로로 가지 않음
  • DFS를 활용하여 구현
  • 백트래킹을 활용하여 불필요한 경로를 조기에 차단

그래프

• 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계 표현
• 정점(Vertex): 그래프의 구성요소. 노드
• 간선(Edge): 정점과 정점 사이 선
• 차수(Degree): 정점에 연결된 간선 수
• 그래프는 정점과 간선으로 구성되어 있으며, 무방향 그래프의 경우 최대 간선은 $V(V-1)/2$, 유방향 그래프의 경우 $V(V-1)$이다.
• 다대다의 관계를 가짐
• 인접: 두 개의 정점 사이 간선이 존재할 경우
• 경로: 어떤 정점에서 다른 정점으로 이르는 사이 간선을 순서대로 나열
• 단순 경로: 시작과 끝을 제외하고 중복이 없는 경로
• 싸이클(Cycle): 경로의 시작 정점과 끝 정점이 같음

인접 행렬(Adjacent matrix)

• V * V 크기의 2차원 배열을 이용하여 간선 정보 저장
• 행 번호와 열 번호는 그래프 정점에 대응
• 인접하면 1(혹은 가중치), 아니면 0

인접 리스트(Adjacent list)

• 각 정점마다 다른 정점으로 나가는 간선의 정보 저장