2606_바이러스 (JAVA)

2606번: 바이러스

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int N;
	static int M;
	static int[][] com;
	static int[] visited;
	static int ans=0;
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		com = new int[N+1][N+1];
		visited = new int[N+1];

		for(int i=0; i<M; i++){
			int temp1 = sc.nextInt();
			int temp2 = sc.nextInt();
			com[temp1][temp2]=com[temp2][temp1]=1;
		}

		BFS(1);
		System.out.println(ans);
	}
	public static void BFS(int n){
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(n);
		visited[n] = 1;

		while(!q.isEmpty()){
			int cur = q.poll();
			for(int i=1; i<=N; i++){
				if(com[cur][i]==1 && visited[i]==0){
					q.offer(i);
					visited[i]=1;
					ans++;
				}
			}
		}
	}
}

 

방향성이 있는 그래프에서는 1->2와 2->1이 다른 경우이고,

방향성이 없는 그래프에서는 1->2와 2->1이 같은 경우이다.

이거를 생각하지 못하고! 1-2가 연결되어 있을때, com[1][2]만 1로 초기화해서 틀렸습니다원인을 못찾았다ㅠㅠ

com[1][2]=com[2][1]=1 을 모두 1로 초기화해줘야한다!!!

 

 

[문제 풀이 생각 과정]

 

1. 방향성이 '없는' 그래프이므로, 입력받은 수에 대하여 com[x][y]=com[y][x]=1 로 초기화해준다.

 

2. 1과 연결된 것만 찾으면 되므로, 노드 개수만큼 visited[]배열을 만들어준다.

 

3. BFS()함수로 돌려준다