[자바 알고리즘 인터뷰] 12장 그래프

그래프 

- 객체의 일부 쌍(Pair)들이 '연관되어' 있는 객체 집합 구조 

 

오일러 경로 

- 모든 간선을 한 번씩 방문하는 유한 그래프 

 

해밀턴 경로 

- 각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로 

- 최적 알고리즘이 없는 N-P 완전 문제

 

해밀턴 순환

- 해밀턴 경로 중에서 원래의 출발점으로 돌아오는 경로 

 

외판원 문제(Travelling Salesman Problem)

- 한 번만 방문하여 출발지로 돌아오는 경로 중 가장 짧은 경로  

 

 

그래프 순회(Graph Traversal)

- 그래프의 각 정점을 방문하는 과정

 

- 그래프를 인접 리스트로 표현한 예

- 인접 리스트는 출발 노드를 키로, 도착 노드를 값으로 표현 

Map<Integer, List<Integer>> graph = new HashMap<>();

graph.put(1,Arrays.asList(2,3,4));
graph.put(1,Arrays.asList(5));
graph.put(1,Arrays.asList(5));
graph.put(1,Arrays.asList());
graph.put(1,Arrays.asList(6,7));

 

 

 

 

1) 깊이 우선 탐색(Depth-First Search)

 

- 스택 또는 재귀로 구현 

 

재귀 구조로 구현 

public List<Integer> recursiveDFS(int v, List<Integer> discovered) {
    //현재 노드 저장(전위 순회)
    discovered.add(v);
    
    //주변 노드 반복
    for(Integer w : graph.get(v)) {
    	//아직 처리되지 않은 노드라면 깊이 기반 탐색 진행
        if(!discovered.contains(w)) {
        	discovered = recursiveDFS(w, discovered);
        }
    }
    
    //모든 깊이를 탐색하면 리턴
    return discovered;

 

 

스택을 이용한 반복 구조로 표현 

 

- 스택을 이용해 모든 인접 간선을 추출하고 다시 도착점인 정점을 스택에 삽입하는 구조 

public List<Integer> iterativeDFS(int v) {
    //결과 노드를 저장할 리스트 선언
    List<Integer> discovered = new ArrayList<>();
    //스택 선언은 효율적인 ArrayDeque 자료형 선언
    Deque<Integer> stack = new ArrayDeque<>();a
    
    //현재 노드를 스택에 삽입
    stack.push(v);
    //스택이 모두 비워질 때까지 반복
    while(!stack.isEmpty()) {
    	//스택에서 추출
        v = stack.pop();
        //이미 방문한 노드가 아니라면 방문 노드에 추가하고 주변 노드를 모두 스택에 삽입
        if(!discovered.contains(v)) {
        	discovered.add(v);
            //현재 노드에서 연결된 모든 주변 노드를 스택에 삽입
            for(int w : graph.get(v)) {
            	stack.push(w)p;
            }
        }
   }
   
   //더 이상 탐색할 노드가 없으면 리턴
   return discovered;
}

 

 

2) 너비 우선 탐색 (Breadth-First Search)

 

 

- 큐를 이용한 반복 구조로 구현 

public List<Integer> iterativeBFS(int start_v) {
    //결과 노드를 저장할 리스트 선언
    List<Integer> discovered = new ArrayList<>();
    //시작 노드 삽입
    discovered.add(start_v);
   	//큐는 인터페이스이며 자료형 선언은 LinkedList 사용
    Queue<Integer> queue = new LinkedList<>();
    
    //시작 노드 삽입
    queue.add(start_v);
    
    //큐가 모두 비워질 때까지 반복
    while(!queue.isEmpty()) {
    	//큐에서 추출
        int v = queue.poll();
        //현재 노드에서 연결된 모든 주변 노드를 큐에 삽입
        for(int w : graph.get(v)) {
        	//이미 방문한 노드가 아니라면 방문 노드에 추가하고 주변 노드를 모두 큐에 삽입
            if(!discovered.contains(w)) {
            	discovered.add(w);
                queue.add(w);
             }
          }
   }
   
   //더 이상 탐색할 노드가 없으면 리턴
   return discovered;
}

 

 

백트래킹(Backtracking)

 

- 해결책에 대한 후보를 구축해 나가다 가능성이 없다고 판단되는 즉시 후보를 포기(백트랙 Backtrack)해 정답을 찾아가는 범용적인 알고리즘으로, 제약 충족 문제(Constraint Satisfaction Problem)등에 유용하다. 

 

- DFS와 같은 방식으로 탐색하는 모든 방법을 뜻하며, DFS는 백트래킹의 골격을 이루는 알고리즘이다. 

 

- 백트래킹은 주로 재귀로 구현하며, 알고리즘마다 DFS 변형이 조금씩 일어나지만 기본적으로 모두 DFS의 범주에 속한다. 

 

- 탐색할 필요가 없는 상태를 제외한다는 것인데, 이를 가지치기라고 한다. 

 

 

제약 충족 문제(Constraint Satisfaction Problem,CSP)

 

- 수많은 제약 조건을 충족하는 상태를 찾아내는 수학 문제 

ex) 스도쿠, 십자말풀이, 8퀸 문제, 4색 문제, 배낭문제, 문자열 파싱, 조합 최적화 등