[알고리즘] 탐색알고리즘 (DFS / BFS)

들어가면서

오늘은 알고리즘 스터디에서 DFS와 BFS를 사용하여 문제를 풀기로 하였다. 탐색 알고리즘인 DFS와 BFS에 대해 알아보자.

---

탐색 알고리즘이란?

• 방대한 데이터에서 목적에 맞는 데이터를 찾아내기 위한 알고리즘
• 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘

1 ) 그래프란?

• 정점과 간선으로 구성된, 한정된 자료구조를 의미한다.
• 각가의 지점을 정점이라고 하고, 정점과 정점의 연결을 간선이라고 한다.

2 ) 활용

네비게이션 경로 문제

- 여러 개의 도시와, 도시를 연결하는 도로의 목록이 주어진다.
- 한 도시가 다른 도시와 연결되어 있는지 알 수 있는가?
- 위의 계산을 정해진 시간 내에, 효율적으로 할 수 있는가?

암시적 그래프 표현

- 그래프가 아니지만 그래프 탐색 알고리즘을 활용해 풀 수 있는 문제.
- 데이터의 형태에 따라 정점으로 간선 대신 x,y좌표로 각 위치를 표현한다.

미로에서 경로 찾기 문제(암시적 그래프표현)

- NxM크기의 배열로 표현되는 미로가 주어진다.
- 미로의 출발점과 도착점은 연결되어 있는가?
- 위의 계산을 정해진 시간 내에, 효율적으로 할 수 있는가?

---

DFS 알고리즘

• Depth First Search로 깊이 우선 탐색을 뜻한다.
• 다음 분기로 넘어가기전 해당 분기를 완벽하게 탐색하고 넘어가는 방법
• 현재 정점과 연결된 정점들을 하나씩 갈 수 있는 지 검사하고, 특정 정점으로 갈 수 있다면 그 정점에서 같은 행위를 반복한다.(깊게 탐색)
• 모든 정점을 방문하고자 할 경우 DFS를 선택한다.
• 같은 정점을 다시 방문하지 않도록 한번 방문한 정점에 표시를 해준다.
• 재귀 함수를 통해 구현

DFS 작동원리

시작점에서 한 갈래로 더 이상 갈 수 없을 때까지 탐색하고, 더 갈 곳이 없다면 이전의 경로로 되돌아간다.

- 그래프 구현

/**
* visit(node_id) : id가 node_id 인 정점을 방문한 것으로 표시
* linked_node(node_id) : 현재 정점(node_id)와 연결된 다른 정점의 목록 반환
* is_visit(node_id) : id가 node_id인 정점을 방문했는지 여부를 반환
*/
void DFS_Graph(int nodeId) {
	// 방문했다는 것을 먼저 표시
    visit(nodeId);
    
    // 연결된 그래프들을 확인
    for(Node node : linkedNode(nodeId)){
    	// 아직 방문하지 않은 경우, 재귀적으로 탐색.
    	if (isVist(node.getId()) != true) {
    		DFS_Graph(node.getId());
    	}
    }
}

- 2차원 이동 구현

/**
* visit(x, y) : 좌표값이 x,y인 정점을 방문한 것으로 표시.
* isValid(x, y) : 좌표값이 x,y인 정정점을 방문할 수 있는지, 좌표값이 유효한지 반환
*/
void DFS_Coordinate(int x, int y) {
	// 방문했다는 것을 먼저 표시
    visit(x,y);
    
    // 위로 이동
    if(isValid(x, y - 1)){
    	DFS_Coordinate(x, y - 1);
    }
    
    // 아래로 이동
    if(isValid(x, y + 1)){
    	DFS_Coordinate(x, y + 1);
    }
    
    // 왼쪽으로 이동
    if(isValid(x - 1, y)){
    	DFS_Coordinate(x - 1, y);
    }
    
    // 오른쪽으로 이동
    if(isValid(x + 1, y)){
    	DFS_Coordinate(x + 1, y);
    }
}

DFS의 장점

• 코드가 직관적이고 구현하기 쉬움(재귀함수를 이해했다는 전제)

DFS의 단점

• 재귀함수를 이용하기에 함수 호출비용이 추가로 들어감.
• 재귀 깊이가 지나치게 깊어지면 메모리 비용을 예측하기 어렵다.
  데이터 사이즈가 일정 이상이면 DFS를 사용하지 않는 것이 좋음.
• 최단 경로를 알 수 없다.

---

BFS 알고리즘

• Beradth-First Search로, 너비 우선 탐색을 뜻한다.
• 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘
• 큐(Queue)를 이용하여 구현
• 출발점을 먼저 큐에 넣고, 다음 로직을 반복한다.

  1) 큐에 저장된 정점을 하나 Dequeue한다.
  2) 그리고 Dequeue된 정점과 연결된 모든 정점을 큐에 넣는다.
  3) 큐가 비어있다면 반복을 종료한다.

• 두 노드사이의 최단 경로, 혹은 임의의 경로를 찾고 싶을 때 주로 사용
• 깊이 우선 탐색보다 좀 더 복잡

BFS 작동원리

- 그래프

- 2차원

시작점 기준으로 거리가 1인 모든 지점을 탐색하고, 이후 2인 지점을 탐색하는 식으로 모든 지점을 탐색한다.
목표 지점을 찾으면 탐색을 종료하고, 찾지 못했다면 연결된 모든 지점을 탐색한다.

- 그래프 구현

/**
* visit(node_id) : id가 nodeID 인 정점을 방문한 것으로 표시
* linked_node(node_id) : 현재 정점(node_id)와 연결된 다른 정점의 목록 반환
* isVisit(node_id) : id가 nodeID인 정점을 방문했는지 여부를 반환
* targetId : 목적지의 ID 값
*/

void BFS_Graph(int startNodeId){
	// 시작 지점을 먼저 넣어준다.
    queue.push(startNodeId);
    
    while(queue.isNotEmpty()) {
    	//위치를 하나 뽑아, 방문 처리를 해준다.
        Long nodeId = queue.pop();
        visit(nodeId);
        
        if(targetId.equals(node.getId())) {
        	return;
        }
        
        // 연결된 다른 정점들을 순회한다.
        for(Node node : linkedNode(0 nodeId)) {
        	if(isVisit(node.getId()) != true) {
            	queue.push(node.getId());
            }
        }
    }
}

1. 시작점을 큐에 넣는다. 이후 큐가 빌때까지 루프를 돌린다.
2. 큐의 제일 앞에 있는 정점을 뽑는다.
   A. 뽑은 지점과 연결된 정점을 큐에 추가한다.
   B. 뽑은 지점이 목표정점이라면 루프를 종료한다.
3. 목표지점을 찾지 못하더라도, 더 갈 수 있는 지점이 없으면 루프는 종료.

2차원 이동 구현

/**
* visit(x, y) : 좌표값이 x,y인 정점을 방문한 것으로 표시.
* isValid(x, y) : 좌표값이 x,y인 정정점을 방문할 수 있는지, 좌표값이 유효한지 반환
* targetPosition : 목적지 위치 좌표값
*/
void DFS_Coordinate(int x, int y) {
	// 시작 지점을 먼저 넣어준다.
    queue.push(new Position(start_x, start_y));
    
    while(queue.isNotEmpty()) {
    	// 위치를 하나 뽑는다.
    	Position position = queue.pop();
   
   		// 방문 처리를 해주고, 만약 목적지라면 로직을 끝낸다.
        visit(position.x, position.y);
        if (tartgetPosition.Equals(position)) {
        	return;
        }
        
    	// 위로 이동
    	if(isValid(position.x, position.y - 1)){
        	queue.push((position.x, position.y - 1);
    	}
    
    	// 아래로 이동
    	if(isValid(position.x, position.y + 1)){
        	queue.push((position.x, position.y + 1);
    	}
    
    	// 왼쪽으로 이동
    	if(isValid(position.x - 1, position.y)){
        	queue.push((position.x - 1, position.y);
    	}
    
    	// 오른쪽으로 이동
    	if(isValid(position.x + 1, position.y)){
        	queue.push((position.x + 1, position.y);
    	}
    }
}

BFS의 장점

• 효율적인 운영이 가능하고, 시간/공간 복잡도 면에서 안정적이다.
• 간선의 비용이 모두 같을 경우, 최단 경로를 구할 수 있다.
  - 간선의 비용이 각각 다를 경우, 다익스트라 알고리즘 등의 최단거리 알고리즘을 활용해야 한다.

BFS의 단점

• DFS에 비해 코드 구현이 어렵다.
• 모든 지점을 탐색할 경우를 대비해, 큐의 메모리가 미리 준비되어 있어야 한다.

---

응용 알고리즘 : Flood Fill Algorithm
최단 경로를 찾을 필요 없이, 연결된 공간이 몇개인지 알아야 할 때 활용.

데이터의 크기가 크지 않은 경우, 단순한 DFS 만으로 문제를 풀 수 있다.
규모가 큰 경우 BFS를 사용하기도 함.

---

응용하여 풀어볼 문제
https://acmicpc.net/problem/14502

BAEKJOON Online Judge
1260 DFS와 BFS : 그래프에서 DFS / BFS연습
2606 바이러스 : 그래프에서 DFS 활용 연습
2667 단지 번호 붙이기 : DFS를 이용한 Flood Fill 연습
2178 미로탐색 : BFS로 4방향 탐색하는 연습
7569 토마토 : BFS로 6방향 탐색하는 연습

---

참고

[10분 테코톡] 📚카프카의 탐색 알고리즘
위키피디아-깊이 우선 탐색 / 너비 우선 탐색
탐색알고리즘(DFS/BFS)