BFS 알고리즘

문제

https://www.acmicpc.net/problem/2606

풀이

BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다

BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

시간초과와 노드정보를 담기위해 인접리스트 사용 : ArrayList[] A;

바이러스는 한 쪽만 연결되어도 전염되기 때문에 노드의 정보를 양쪽에 저장 :A[a].add(b);
A[b].add(a);

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B2606 { 
	static int n;
	static int m;
	static int count;
	static boolean visited[];
	static ArrayList<Integer>[] A;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		A = new ArrayList[n+1];
		
		visited = new boolean[n+1];
		for (int i = 1; i <=n; i++) {
			A[i] = new ArrayList<Integer>();	
		}
		
		StringTokenizer st ;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			A[a].add(b);
			A[b].add(a); //연결만 되어있으면 바이러스에 걸리니간 양 인덱스값에추가 해 줘야됨
			
		}
		int result= dfs(1);
		System.out.println(result);
		
		
	}
	private static int dfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(start);
		visited[start] =true;
			
			while(!q.isEmpty()) {
				
				int next= q.poll();
				for (int i : A[next]) {
					if(visited[i] ==false) {
						visited[i]=true;
						q.add(i);
						count++;
					}			
				}
		
			}
		return count;	
	}
}