백준 2606 - BFS(Breadth-First-Search)

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);
		
		
	}

}