1. BFS(너비 우선 탐색)
BFS vs DFS
-동작과정
- 큐 선언(2차원 배열이라면 Point 클래스를 활용) 및 시작 포인트 큐에 추가&&방문체크
- while(!Queue.isEmpty()) 큐가 없어질 때까지 반복
- Queue에서 poll하여 탐색 시작
- 방향벡터를 이용해서 for문 4방탐색
- 다음 행선지 NULL체크
- 탈출 포인트 선언 (예를 들어 목적지 좌표에 도착했다면)
- 장애물 및 가지 말아야하는 곳이라면 continue로 탈출
- 탐색할 수 있는 곳이라면 방문체크 및 큐 추가 (제약사항들에 대한 조건문 추가)
-완전탐색 방식
- Queue자료형의 선입선출 특성을 활용
- 현재 지점에서 4방향에 탐색할 수 있는 곳들을 전부 큐에 추가
- 큐에 추가할 때는 한 개의 전역변수 느낌이 아닌 new키워드로 다른 객체를 추가함으로써 재귀와 같이 별도의 데이터를 관리
- 추가된 큐에 대해 한 개씩 poll해보며 완전탐색
- DFS의 경우 재귀스택을 활용한 좌표 별 데이터 관리
- BFS는 개별 객체를 통해 좌표 별 데이터 관리 (즉, 바뀌어야할 매개변수가 있다면 객체 멤버변수를 활용)
-특성
- 최단경로를 찾기위한 알고리즘으로써 DFS에 비해 속도면에서 우위를 가짐
- 미로찾기와 같은 최우선의 특정 경로를 찾는 문제에서 BFS를 떠올릴 수 있음
- DFS의 경우 먼저 탐색한 곳 쪽으로 계속 탐색을 진행하지만 BFS의 경우 현재좌표 근처로 확산하며 탐색.
- DFS : 4.0 → 3.0 → 2.0 → 1.0 → 0.1 → …
- BFS : 4.0 → 3.0 → 4.1 → 2.0 → 4.2 → …
-구현
- Graph
public class Main{ static int N, M, V; //정점 수, 간선 수, 시작 노드 static int[][] graph; static boolean[] visited; public static void main(String[] args) { /* 이 곳에 입력 및 배열 초기화를 진행하고, 배열크기에 맞게 visited배열 선언 */ bfs(V); } //너비 우선 탐색 (그래프로 풀 경우 간선의 존재 유무만 체크하면 됨) static void bfs(int idx) { Queue<Integer> queue = new LinkedList<Integer>(); //큐 선언 queue.add(idx); //큐에 시작지점을 추가 visited[idx] = true; //방문체크 while(!queue.isEmpty()){ //큐가 빌 때까지 무한루프 int s =queue.poll(); //현재 큐에 들어있는 맨 앞의 값을 꺼냄 for(int i =1; i< graph.length;i++){ //그래프의 길이만큼 반복하면서 if(graph[s][i] == 1 && !visited[i]){ //간선이 있을 때&&방문하지 않은 경우 queue.add(i); //큐에 계속해서 추가 visited[i] = true; //방문체크 } } } } } - 사방탐색
class Point{ //좌표값을 저장하기 위한 Point 클래스 int x; int y; public Point(int x, int y){ this.x = x; this.y = y; } } public class Main{ static int[] dx = new int[] {-1, 0, 1, 0}; //방향벡터 static int[] dy = new int[] {0, 1, 0, -1}; //방향벡터 static int N, M, V; //정점 수, 간선 수, 시작 노드 static int[][] map; static boolean[][] visited; public static void main(String[] args) { /* 이 곳에 입력 및 배열 초기화를 진행하고, 배열크기에 맞게 visited배열 선언 */ bfs(0, 0); //어디서부터 탐색을 할 지 } //너비 우선 탐색 (그래프가 아닌 단순 2차원 배열 좌표값을 활용할 때 static void bfs(int x, int y) { Queue<Point> q = new LinkedList<>(); //큐 선언 visited[x][y] = true; //시작지점 방문체크 q.offer(new Point(x,y)); //큐에 시작지점 추가 while(!queue.isEmpty()){ //큐가 빌 때까지 무한루프 Point p = q.poll(); // 맨 앞의 큐를 꺼내고 for (int i = 0; i < 4; i++) { //큐에서 꺼낸 인덱스로부터 사방탐색 if (p.x + dx[i] < 0 || p.x + dx[i] > N - 1 || p.y + dy[i] < 0 || p.y + dy[i] > N - 1) continue; //Null 예외 처리 if(특정 조건 값){ visited[p.x + dx[i]][p.y + dy[i]] = true; //방문 체크 q.offer(new Point(p.x + dx[i], p.y + dy[i])); //탐색을 위한 큐 추가 } //4방탐색을 돌면서 해야할 조건들을 추가** } } } }
Hello, World!