Algorithm : 그래프의 탐색_BFS
BFS
: Breadth-First-Search, 시작 정점으로부터 가장 가까운 정점을 먼저 방문하고, 멀리 떨어져있는 정점을 나중에 방문한다. 루트 노드나 임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.
BFS의 특징
- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
- 큐를 이용해 반복적 형태로 구현한다.
- 노드 방문 여부를 확인해야 한다. 그렇지 않을 경우 무한 루프에 빠질 위험이 있다.
BFS의 구현
인접 리스트를 이용한 구현
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
public class Main {
static int V, S; // V는 정점의 개수, S는 탐색을 시작할 정점 번호
static int x, y; // x와 y 사이의 경로가 존재
static ArrayList<ArrayList<Integer>> graph;
static ArrayList<Integer> bfs;
static boolean[] visited;
static Queue<Integer> queue;
public static void bfs() {
bfs = new ArrayList<Integer>();
visited = new boolean[V + 1];
queue = new LinkedList<Integer>();
queue.offer(S);
visited[S] = true;
while(!queue.isEmpty()) {
int q = queue.poll();
bfs.add(q);
for(int i : graph.get(i)) {
if(!visited[i]) {
queue.offer(i);
visited[i] = true;
}
}
}
}
public static void main(String[] args) {
// V, S initial
graph = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < V+1; i++)
graph.get(i).add(new ArrayList<Integer>());
for(int i = 0; i < V+ 1; i++) {
// input x, y
graph.get(x).add(y);
graph.get(y).add(x);
} // 양방향 추가
bfs();
for(int i = 0; i < bfs.size(); i++)
System.out.println(bfs.get(i) + " ");
}
}
BFS 알고리즘 코드
출처 : 2667번: 단지번호붙이기 (acmicpc.net)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;
import java.util.LinkedList;
class Dot {
int x;
int y;
public Dot(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
public static int N;
public static int[][] map;
public static boolean[][] visited;
public static ArrayList<Integer> answer;
public static Queue<Dot> queue;
public static int[] rowArr = {-1, 0, 1, 0};
public static int[] colArr = {0, -1, 0, 1};
public static void bfs(int i, int j) {
queue.offer(new Dot(i, j));
int count = 1;
while(!queue.isEmpty()) {
Dot dot = queue.poll();
visited[dot.x][dot.y] = true;
for(int k = 0; k < 4; k++) {
int row = dot.x + rowArr[k];
int col = dot.y + colArr[k];
if(checkDot(row, col)) {
count += 1;
map[row][col] = count;
queue.add(new Dot(row, col));
}
}
}
answer.add(count);
}
public static boolean checkDot(int row, int col) {
if(row >= N || col >= N || row < 0 || col < 0)
return false;
if(map[row][col] != 1 || visited[row][col] == true)
return false;
return true;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
visited = new boolean[N][N];
answer = new ArrayList<Integer>();
queue = new LinkedList<Dot>();
for(int i = 0; i < N; i++) {
String line = br.readLine();
for(int j = 0; j < N; j++)
map[i][j] = line.charAt(j) - '0';
}
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(map[i][j] == 1 && visited[i][j] == false)
bfs(i, j);
Collections.sort(answer);
StringBuilder sb = new StringBuilder();
sb.append(answer.size()).append("\n");
for(int i = 0; i < answer.size(); i++)
sb.append(answer.get(i)).append("\n");
System.out.println(sb);
}
}
BFS 참고 사이트
반응형
'Programando > Algorithm' 카테고리의 다른 글
힙(Heap) (0) | 2021.08.08 |
---|---|
그래프의 탐색_DFS (0) | 2021.07.19 |
그래프(Graph) (0) | 2021.07.11 |
덱과 JAVA Deque 클래스 (0) | 2021.06.18 |
큐와 JAVA Queue 클래스 (0) | 2021.06.15 |