참고로 풀어볼 만한 문제 모음
너비우선탐색(BFS)란?
너비 우선 탐색은 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법으로 깊게(deep) 탐색하기 전에 넓게(wide) 탐색한다고 하여 너비우선탐색이라고 불린다.
너비우선탐색의 특징과 작동 원리
- BFS는 재귀적으로 동작하지 않는다.
- 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
- BFS는 방문한 노드를 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(Queue)를 사용한다.
깊이가 1인 모든 노드를 방문하고 나서 그 다음에 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.
위의 그림을 보면 우선
1. a 노드(시작노드)에 방문한다: 방문한 노드는 queue에 넣는다.
2. queue에서 꺼낸 노드와 인접한 노드들을 차례대로 방문한다: queue에서 방문 노드를 꺼내 해당 노드와 인접한 노드들을 1과 같은 방법으로 방문한다. 인접한 노드가 없다면 큐에서 노드를 꺼낸다.
3. queue가 empty 상태가 될 때까지 반복한다.
너비우선탐색(BFS)의 구현
void search(Node root) {
Queue queue = new Queue();
root.marked = true; // (방문한 노드 체크)
queue.enqueue(root); // 1-1. 큐의 끝에 추가
// 3. 큐가 소진될 때까지 계속한다.
while (!queue.isEmpty()) {
Node r = queue.dequeue(); // 큐의 앞에서 노드 추출
visit(r); // 2-1. 큐에서 추출한 노드 방문
// 2-2. 큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문한다.
foreach (Node n in r.adjacent) {
if (n.marked == false) {
n.marked = true; // (방문한 노드 체크)
queue.enqueue(n); // 2-3. 큐의 끝에 추가
}
}
}
}
너비우선탐색(BFS) 활용
너비우선탐색을 사용하는 경우는 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
최단거리, 최소비용, 최단시간을 구할 때 주로 쓴다.
BFS를 사용할 때 간과하게 쉬운 것이 가장 적게 이동해서 목표지점에 도달하는 것만이 BFS라고 생각하기 쉬운데 사실 그렇지 않다.
BFS와 DP를 같이 활용하면 꼭 가장 적게 이동한 경우 중에서 최소비용을 비교하여 따져볼 수 있다.
BFS + DP
이 방법은 최단경로의 경우가 여러개일 때 각 비용을 따져서 비교하고 싶을때 쓴다
BFS의 기본은 다음 노드에 방문하지 않은 경우 queue에 넣기 전에 방문처리한 후 넣어주는 것이다.
그래야 중복적인 방문을 막을 수 있기 때문이다.
그런데 단순히 최단경로만 계산할 경우 이 방법이 통하지만, 만약 부수적으로 경로에 따라 비용이 다르다든지 예외적인 상황이 있는 경우 BFS와 DP를 활용해서 조건을 추가할 수 있다.
이럴 경우 visit 대신 dp를 두고 dp 값이 아직 업데이트가 안된 (방문이 안된) 노드를 방문하거나 혹은 현재 계산 값이 같은 route로 미리 계산되어서 업데이트 되었던 dp 값보다 작은 경우(혹은 목표하는 값과 더 가까울 경우 등) 새롭게 이미 왔던 경로도 다시 방문하고 dp를 업데이트 한다.
이 때 중요한 것은 다음 노드에 방문하려고 할 때, 단순히 방문 여부만 따져서 방문 안한 노드만 방문하려고 하지말고, 만약 이미 방문했지만 지금 업데이트할 비용이 이전에 저장되어있던 비용보다 싼 경우 다시 업데이트하고 queue에 넣는 것으로 구현하는 것이다.
이동 방향에 따라 비용이 달라지는 경우에는 방향에 따라 루트를 다르게 두어야 한다.
https://programmers.co.kr/learn/courses/30/lessons/67259
이 문제를 참고하면 이해가 빠를 것이다.
길을 탐색할 때 등 방향에 따라(혹은 상황에 따라) 같은 경로로 이동하더라도 결과적으로 구하고자 하는 값은 경우에 따라 다른 문제가 있다.
이 문제도 이전에 동서남북 중 어디에서 와서 지금의 노드에 방문했냐에 따라 다음 노드로 가는 값이 달라진다.
따라서 단순히 노드를 방문하는 경로로는 해결할 수 없고, 4방의 방향까지 고려해서 경로를 새롭게 따져주어야 한다.
즉, (1,1) 에서 (1,2)로 가는 경우는 하나가 아니라 (N,1,1)에서 (E,1,1) 이런 식으로 4방의 경우가 따로 dp에 저장되어야 한다.
이런 경우 결국에는 dfs랑 똑같아 지는거 아닌가 라는 생각이 들게 된다. 4방의 경우를 모두 결국 방문해야 하기 때문이다.
효율은 PriorityQueue로 높인다
이런 경우 효율은 PriorityQueue로 높일 수 있다.
기존의 bfs는 일반 queue만으로 계산을 했었는데, priorityQueue를 이용해서 만약 같은 경로가 queue안에 여러 개 들어가 있는 경우 들어간 순서대로 하나씩 다 방문해주게 되면 최솟값 업데이트가 그만큼 늦어지므로
queue안의 중복 경로 중 가장 비용이 작은 순으로 꺼낸다.
이렇게 하면 가장 작은 비용이 먼저 update가 되기 때문에 이후에 더 큰비용의 같은 경로를 만나면 따로 다시 bfs로 탐색할 시간이 훨씬 줄어들게 된다.
import java.util.*;
import static java.lang.Math.min;
class Solution {
public int solution(int[][] board) {
Jordy jordy = new Jordy(0, 0);
int[][][] moneyCheck = new int[board.length][board.length][4];
this.initMoneyCheck(moneyCheck);
return this.getMinimumMoney(jordy, board, moneyCheck);
}
private void initMoneyCheck(int[][][] moneyCheck){
for(int i = 0; i < moneyCheck.length; i++)
for(int j = 0; j < moneyCheck.length; j++)
for(int l = 0; l < 4; l++) moneyCheck[i][j][l] = 987654321;
}
private int getMinimumMoney(Jordy jordy, int[][] board, int[][][] moneyCheck){
PriorityQueue<Jordy> jordies = new PriorityQueue<Jordy>();
jordies.add(jordy);
while(!jordies.isEmpty()){
Jordy nowJordy = jordies.poll();
if(nowJordy.isJordyOnWall(board) || nowJordy.isExpensiveCase(moneyCheck)) continue;
for(int i = 0; i < 4; i++){
Jordy nextJordy = nowJordy.move(i);
if(nextJordy.isOutOfBounds(board.length)) continue;
jordies.add(nextJordy);
}
}
return min(
min(moneyCheck[moneyCheck.length-1][moneyCheck.length-1][0], moneyCheck[moneyCheck.length-1][moneyCheck.length-1][1])
, min(moneyCheck[moneyCheck.length-1][moneyCheck.length-1][2], moneyCheck[moneyCheck.length-1][moneyCheck.length-1][3])
);
}
}
class Jordy implements Comparable<Jordy>{
private int y, x;
private int dir;
private int money;
private static final int[] dy = {-1, 0, 1, 0};
private static final int[] dx = {0, -1, 0, 1};
private static final int corner = 500;
private static final int straight = 100;
public Jordy(int y, int x){
this.y = y;
this.x = x;
this.dir = -1;
this.money = 0;
}
public Jordy(int y, int x, int dir, int money){
this(y, x);
this.dir = dir;
this.money = money;
}
public boolean isJordyOnWall(int[][] board){
return board[this.y][this.x] == 1;
}
public boolean isExpensiveCase(int[][][] moneyCheck){
if(this.dir == -1) return false;
if(this.money > moneyCheck[this.y][this.x][this.dir]) return true;
moneyCheck[this.y][this.x][this.dir] = this.money;
return false;
}
public boolean isOutOfBounds(int bound){
if(this.y >= bound || this.x >= bound || this.y < 0 || this.x < 0) return true;
return false;
}
public Jordy move(int dir){
return new Jordy(this.moveY(dir), this.moveX(dir), dir, this.addMoney(dir));
}
private int moveY(int dir){
return this.y + this.dy[dir];
}
private int moveX(int dir){
return this.x + this.dx[dir];
}
private int addMoney(int dir){
if(this.dir == -1 || this.dir == dir) return this.money + this.straight;
return this.money + this.corner + this.straight;
}
public int getY(){
return this.y;
}
public int getX(){
return this.x;
}
public int getMoney(){
return this.money;
}
@Override
public int compareTo(Jordy jordy){
if(this.money > jordy.getMoney()) return 1;
if(this.money < jordy.getMoney()) return -1;
return 0;
}
}너비우선탐색의 시간복잡도
- 인접 리스트로 표현된 그래프 O(N+E)
- 인접 행렬로 표현된 그래프 O(N^2)
예시1
지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
- 깊의 우선 탐색 - 모든 친구 관계를 다 살펴봐야 할지도 모름
- 너비 우선 탐색 - Ash와 가까운 관계부터 탐색
예시2
여러개의 블록 또는 좌표가 서로 인접한지 확인하는 경우
상세 예시1) 각 노드들이 행렬에서 인접한 관계인지 파악하기
- 참고문제 : 백준[1941] 소문난 칠공주
상세 예시2) 시작 점에서 끝 점까지 도달하는 최단 루트(시간) 구하기
- 참고문제 : 백준[1679] 숨바꼭질
너무 DP에만 매몰되어 있어서 BFS 를 쓸 거라고 생각도 못했다 😭
따지고보면 완전 BFS를 위한 문제였는데.. 아직 BFS가 익숙하지 않아서 그런거겠지
나중에 다시 풀어보자
