⚡ 그래프 (2)
📌 그래프 탐색
🔷 트리(그래프, 2차원 배열) 순회(탐색)
- 모든 자료를 빠짐 없이 탐색하는 것
⭐ 깊이 우선 탐색 (Depth First Search, DFS)
🔷 루트 노드(시작 정점, 출발 위치)에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드(정점)로 되돌아와서 다른 방향의 노드(정점)으로 탐색을 계속 반복하여 결국 모든 노드(정점)을 방문하는 순회방법
- 가장 마지막에 만났던 갈림길의 노드(정점)로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출(LIFO) 자료구조인
스택사용 - 재귀 함수는 시스템 스택을 이용하므로 이를 이용하여 간단하게 구현할 수도 있다.
🔷 탐색 방법(stack)
1) 루트 노드를 stack에 push한다.
2) stack에서 노드(curr)를 pop한다.
3) curr의 모든 자식 노드를 stack에 push한다.
4) stack이 공백 상태가 될 때까지 2)-3)을 반복한다.
🔷 탐색 방법(재귀 함수)
1) 현재 노드(V) 방문
2) (V)의 자식 노드 (W)를 차례로 재귀 호출
❗ 재귀로 그래프 탐색 시 주의점
1. 트리와 다르게 그래프 탐색 시에는 탐색한 곳을 되돌아가 중복 탐색할 수 있다. 무한 재귀 지옥에 빠질 수 있으므로 visited 처리를 위한 boolean 배열을 따로 선언하여 사용해주자.
2. 인접 행렬 탐색시 범위 체크 중 배열 범위를 벗어날 수 있다. 오류 방지를 위해 2차원 배열의 x, y를 1씩 더 크게 선언한 뒤에 탐색하지 않게 하는 임의의 값을 넣으면 편리하다.
public class DailyAPS {
static int N = 7;
//인접 행렬
static int [][] adj = {
{ 0, 1, 1, 0, 0, 1, 0 },
{ 1, 0, 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 1, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 1, 1 },
{ 1, 0, 0, 0, 1, 0, 0 },
{ 0, 1, 0, 1, 1, 0, 0 }
};
static boolean[] visited = new boolean[N]; //방문처리를 할 배열
public static void main(String[] args) {
DFS(2);
}
//인자로 현재 내가 방문하고 있는 정점이 들어온다.
static void DFS(int v) {
//v에 대한 방문처리
visited[v] = true;
System.out.println(v+1); //그래프가 1부터 시작한다고 가정하고 1을 더했다
//방문하지 않았으면서, 연결된 간선이 존재한다면 재귀 호출
for(int i = 0; i < N; i++) {
if(!visited[i] && adj[v][i] == 1) {
DFS(i);
}
}
}
}
⭐ 너비 우선 탐색 (Breadth First Search, BFS)
🔷 루트 노드(시작 정점, 출발 위치)의 자식 노드(인접한 정점)들을 먼저 모두 차례로 방문한 후에 방문했던 자식 노드들(인접한 정점)을 시작점으로 하여 다시 해당 노드의 자식 노드(인접한 정점)들을 차례로 방문하는 방식
- 자식 노드(인접한 정점)들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출(FIFO) 자료구조인
큐를 활용 - 너비 우선 탐색은 인접한 노드들 부터 차례대로 방문을 하므로 시작 정점과 끝 정점이 주어졌을 때 최단 길이를 구할 수 있다.
🔷 탐색 방법(queue)
1) 루트 노드를 queue에 삽입
2) queue에서 원소(curr) 꺼내기
3) 해당 원소 방문 처리
4) curr의 자식 노드를 queue에 삽입
5) queue가 공백이 될 때까지 2)~5) 반복
import java.util.LinkedList;
import java.util.Queue;
public class DailyAPS {
static int N = 7;
//인접 행렬
static int [][] adj = {
{ 0, 1, 1, 0, 0, 1, 0 },
{ 1, 0, 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 1, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 1, 1 },
{ 1, 0, 0, 0, 1, 0, 0 },
{ 0, 1, 0, 1, 1, 0, 0 }
};
static boolean[] visited = new boolean[N]; //방문처리를 할 배열
static Queue<Integer> queue = new LinkedList<Integer>();
public static void main(String[] args) {
BFS(0);
}
//v: 시작정점
static void BFS(int v) {
//시작정점을 큐에 넣는다.
queue.add(v);
visited[v] = true; //방문처리
//큐가 공백이 될 때까지 반복
while(!queue.isEmpty()) {
//정점을 하나 꺼낸다
int t = queue.poll();
System.out.println(t+1); //1부터 시작한다고 가정
//t와 연결되어 있으면서 방문하지 않는 정점들은 queue에 넣고 방문처리를 한다
for(int i = 1; i < N; i++) {
if(!visited[i] && adj[t][i] == 1) {
queue.add(i); //큐에 넣고 방문처리
visited[i] = true;
}
}
}
}
}
🔷 최단 길이 구하는 방법
1) 2차원 배열을 만들어 직접 길이를 저장한다.
2) 큐에 넣을 때 같이 넣어 저장한다. (큐 생성시 Integer[]로 생성 or 클래스 멤버 변수로 함께 저장)
3) 길이를 저장하는 변수를 생성하여 이를 활용한다. (Queue size를 묶어 같은 레벨끼리 처리)
중요 파트!
