알고리즘 && 자료구조
백준 2606 - BFS(Breadth-First-Search)
bloodFinger
2020. 6. 8. 21:53
BFS의 대표적인 문제이다.
개념만 이해하고 있다면 간단하게 이해하고 풀수있는 수준이다.
문제
https://www.acmicpc.net/problem/2606
해설
public class P_2606 {
private int node[][];
private int check[];
private int bfs(int start) {
Queue<Integer> que = new LinkedList<Integer>();
int dap =0;
que.offer(1);
while(!que.isEmpty()) {
int val = que.poll();//값을 꺼낸다.
check[val] = 1; //확인한 값은 배열에 담아둔다.
for (int i = 0; i < node.length; i++) {
if(node[val][i] == 1 && check[i] != 1) {
que.offer(i);
check[i] = 1;
dap++;
}
}
}
return dap;
}
public static void main(String[] args) {
P_2606 p = new P_2606();
Scanner sc = new Scanner(System.in);
int n= sc.nextInt(); // 컴퓨터의 수
int m = sc.nextInt(); // 간선의 수
p.node = new int[n+1][n+1];
p.check = new int[n+1];
for(int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
p.node[a][b]=1;
p.node[b][a]=1;
}
p.bfs(1);
}
}