[ JAVA ] 그래프 이론, 백트래킹

1. 그래프(Graph)

---

1. 그래프란?

• 무방향 그래프: 간선에 방향이 없어 A → B나 B → A가 같은 의미.
• 방향 그래프: 간선에 방향이 있어 A → B와 B → A가 다름.
• 가중 그래프: 간선에 가중치(비용, 거리 등)가 있는 그래프.
• cycle을 도는 방식

---

 

2. 인접 행렬 그래프

 

가중치 X	가중치 O
연결: true, 1	value
비연결: false, 0	0

    

Node 수	인접 행렬	배열 크기	메모리	수행 횟수
100	100*100	10,000	10K, 4K	10,000
1000	1000*1000	1,000,000	1M, 4M	1,000,000
10,000	노드 수가 많으면 인접 행렬 불가	100,000,000	100M, 400M	1억

• 인접 행렬로는 메모리 초과, 시간 초과이므로 불가 → 인접 리스트로 해야 함, 인접 리스트 수행 속도(Node*link)

---

 

3. DFS를 BFS로 바꾸는 주요 방법

• 자료 구조와 노드 처리 구성이 다름

1. 자료구조 변경:
   • DFS에서 사용하는 스택(또는 재귀) 대신 큐(Queue)를 사용합니다.
   • 일반적으로 **ArrayDeque**나 **LinkedList**를 사용하여 큐를 구현합니다.
2. 노드 처리 순서 변경:
   • DFS는 한 경로를 끝까지 탐색하지만, BFS는 현재 깊이의 모든 노드를 먼저 탐색합니다.
   • 큐에서 노드를 꺼내고(poll), 해당 노드의 모든 인접 노드를 큐에 추가합니다(offer).
3. 방문 처리:
   • DFS와 마찬가지로 방문한 노드를 표시하는 배열이나 Set을 사용합니다.
   • 단, BFS에서는 큐에 노드를 추가할 때 방문 처리를 합니다.
4. 반복문 구조:
   • while 루프를 사용하여 큐가 비어있을 때까지 반복합니다.

• 예시 코드 변환_DFS와 BFS

java// DFS는 Stack과 visited, next 사용
void dfs(int start) {
    boolean[] visited = new boolean[N];
    Stack<Integer> stack = new Stack<>();
    stack.push(start);
    
    while (!stack.isEmpty()) {
        int current = stack.pop();
        if (visited[current]) continue;
        
        visited[current] = true;
        System.out.print(current + " ");
        
        for (int next : graph[current]) {
            if (!visited[next]) {
                stack.push(next);
            }
        }
    }
}

*// BFS는 Queue와 visited*
void bfs(int start) {
    boolean[] visited = new boolean[N];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;
    
    while (!queue.isEmpty()) {
        int current = queue.poll();
        System.out.print(current + " ");
        
        for (int next : graph[current]) {
            if (!visited[next]) {
                queue.offer(next);
                visited[next] = true;
            }
        }
    }
}

 

2. 백트래킹(BackTracking)

---

1. 백트래킹이란?

• 불필요한 경로를 조기에 차단하여 탐색을 효율적으로 수행하는 것이 핵심!!!

1-1. *상태 공간 트리(State Space Tree)**를 활용하여 해를 찾음.

1-2. *가능성이 없는 경로를 빨리 포기(Pruning)**하고 되돌아감(Backtrack).

1-3. 재귀(Recursion)를 활용하여 탐색을 수행하는 경우가 많음.

---

 

2. 백트래킹이 유효하지 않은 경우(충돌 발생 시) 즉시 포기하고 이전 단계로 돌아가는 과정

 

2-1. 예시 문제

• • N-Queen 문제
  • 순열 및 조합 생성
  • 미로 탐색 (DFS와 유사)
  • 부분 집합 구하기
  • Sudoku 풀이

2-2. 가능한 모든 해답을 탐색하는 기법