그래프 탐색 구현 flow
그래프 탐색에는 DFS와 BFS이 있습니다.
그래프를 생성하는 과정과 방문기록 배열의 생성은 DFS나 BFS나 동일합니다.
탐색 방식에 따른 구현부만 달라지는데, 보통 둘 다 재귀를 이용해 호출합니다.
1. 그래프 표현하기 및 데이터 저장
adjList생성 (linkedList) 모든adjList를 순회하며 각각 리스트 객체 붙여주기adjList에 에지 추가(데이터)
문제에 따른 엣지 오름/내림 정렬 / 그래프는 보통 양방향 무가중치 그래프이지만 추가시에 유의
2. 방문기록 배열 생성하기
boolean 배열생성
3. 재귀호출
BFS or DFS
DFS
- 깊이 우선 탐색
- 그래프 완전 탐색 기법
- 구현방법 : 재귀함수 / 스택
- 시간복잡도 : O(V+E)
DFS 구현
DFS를 구현하는 방법에는 스택으로 구현하는 방법과 재귀를 이용해서 구현하는 방법이 존재하는데, 재귀함수는 내부적으로 함수가 call될때 메모리에 push되었다 함수가 return할때 pop하기 때문에,
DFS 구현 핵심
- 노드 방문 여부 체크할 배열 생성
- 그래프 표현은 인접리스트를 이용해 만든다.
- linkedList를 이용해 인접리스트를 만들어주고, 각 노드에 대한 인접정점을 담을 공간 또한, linkedList 객체를 각각 붙여줌
- DFS 코드 작성 후 재귀호출
DFS 코드
핵심 : 현재노드를 방문처리하고, 현재노드의 연결노드 중 방문하지 않은 노드를 찾아서 방문하지 않았다면 DFS를 실행한다.
DFS{
if (현재노드 == 방문노드) return
visited 배열에 기록
현재 노드의 연결노드 중 방문하지 않은 노드로 DFS실행
}그래프
static void DFS (int v){
if(visited[v]){
return;
}
visited[v] = true;
for(int i:AdjList[v]){
DFS(i);
}
}
배열
static void DFS(int X, int Y){
visited[X][Y] = true;
// 현재 좌표를 기준으로 상하좌우를 살피고,
for(int i=0; i<4; i++) {
int MX = X + dx[i];
int MY = Y + dy[i];
// 이동시킨 점의 위치가 배추밭 내부의 점이여야 한다
if( MX >= 0 && MX < M && MY >= 0 && MY < N){
// 만약 해당 값이 방문하지 않은 점이고, 값이 1이라면 return
if(board[MX][MY] == 1 && !visited[MX][MY]){
DFS(MX,MY);
}
}
}
}
BFS
- 너비 우선 탐색
- 그래프 완전 탐색 기법
- 구현방법 : 큐(FIFO)
- 시간복잡도 : O(V+E)
BFS 구현
BFS 알고리즘은 목표노드에 도착하는 경로가 여러개일때 최단경로를 보장합니다.
BFS 구현 핵심
- 노드 방문 여부 체크할 배열 생성
- 그래프 표현은 인접리스트를 이용해 만든다.
- linkedList를 이용해 인접리스트를 만들어주고, 각 노드에 대한 인접정점을 담을 공간 또한, linkedList 객체를 각각 붙여줌
- BFS 코드 작성 후 재귀호출
BFS 작동 순서
- 큐에서 노드를 꺼내면서, 인접노드를 큐에 삽입
- 큐에서 꺼낸 노드는 방문기록
- 큐에 노드가 없어질때까지 반복
BFS 코드
핵심 : 큐 자료구조에 시작노드 삽입하고, 큐가 빌 떄 까지 큐에서 노드를 가져오고, 가져온 노드를 출력한다.
그래프
BFS{
큐에 시작 노드 삽입
visited 배열 _현재 노드 방문기록
while(큐가 비어있지 않은 동안에){
큐에서 노드 가져오기
가져온 노드 출력하기
현재 노드의 연결노드 중 미방문 노드를 큐에 삽입하고 방문배열에 기록하기
}
}static void BFS(int Node){
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(Node);
visited[Node] = true;
while(!queue.isEmpty()){
int now_Node = queue.poll();
System.out.println(now_Node+ " ");
for(int i: A[now_Node]) {
if (!visited[i]) {
visited[i] = true;
queue.add(i);
}
}
}
}
배열
static void BFS(int X, int Y){
Queue<int[]> q = new LinkedList<int[]>();
q.add(new int[] {X,Y});
visited[X][Y] = true; // 보통 큐에 값을 넣고 방문처리함
while(!q.isEmpty()){
X = q.peek()[0];
Y = q.peek()[1];
q.poll();
/* q에서 값 꺼내고 인덱스로 접근해도 됨 ~~
int[] current = q.poll();
x = current[0];
y = current[1];
*/
for(int i=0; i<4; i++){
int MX = X + dx[i];
int MY = Y + dy[i];
if( MX >= 0 && MX < M && MY >= 0 && MY < N){
if(board[MX][MY] == 1 && !visited[MX][MY]){
q.add(new int[] {MX, MY});
visited[MX][MY] = true;
}
}
}
}
}