백준 2606 바이러스(자바)

 

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

2606번: 바이러스

 

그래프를 공부하고 BFS를 배우면서 가장 기본적으로 접하게 되는 문제다.

 

그림을 보면 1번과 연결이 된 컴퓨터는 총 4대이다.(1번 제외)

이렇듯 1번 컴퓨터를 통해 바이러스에 걸린 컴퓨터의 수를 출력하면 된다.

 

우선 전체 코드를 보자

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

public class Main {
	static Queue<Integer> q;
	static boolean[] visited;
	static List<Integer>[] list;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		visited = new boolean[V+1];
		q = new LinkedList<Integer>();		
		
		list = new ArrayList[V+1];
		for(int i=0; i<V+1; i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int i=0; i<E; i++) {
			int st = sc.nextInt();
			int ed = sc.nextInt();
			list[st].add(ed);
			list[ed].add(st);
		}
		int cnt = 0;
		BFS(1,0);
		
		
	}
	
	public static void BFS(int depth, int cnt) {
		q.add(depth);
		visited[depth] = true;
		while(!q.isEmpty()) {
			int curr = q.poll();
			for(int i=0; i<list[curr].size(); i++) {
				int temp = list[curr].get(i);
				if(!visited[temp]) {
					visited[temp] = true;
					q.add(temp);
					cnt++;
				}
			}
		}
		System.out.println(cnt);
	}
}

단순하게 BFS를 통해 문제를 풀었다.

BFS는 큐를 이용해서 문제를 풀기 때문에 큐를 사용했다.

DFS랑 BFS 둘 다 푸는 방법이 있지만 나는 BFS가 더 편하다...

 

코드를 천천히 살펴보자

static Queue<Integer> q;
static boolean[] visited;
static List<Integer>[] list;

우선 BFS메서드에서 사용이 가능하게 전부 static으로 선언했다.

BFS라 큐를 사용하기 때문에 큐를 선언했고

방문했는지 확인을 위한 visited 배열, Integer타입의 리스트를 담기 위해 배열을 선언했다.

 

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int V = sc.nextInt();
	int E = sc.nextInt();
	visited = new boolean[V+1];
	q = new LinkedList<Integer>();		
		
	list = new ArrayList[V+1];
	for(int i=0; i<V+1; i++) {
		list[i] = new ArrayList<>();
	}

V는 정점(Vertex), E는 간선(Edge)으로 입력을 받았다.

방문확인을 위한 visited배열은 1번부터 시작하기 때문에 V+1로 생성.

큐도 생성해주고

list 또한 V+1 사이즈로 만들어주었다.

 

list = new ArrayList[V+1];  // 이 부분은 리스트를 담을 수 있는 배열의 사이즈를 생성해 준 것이므로

for문을 돌면서 각 배열마다 리스트 객체를 생성해 주었다.

 

for(int i=0; i<E; i++) {
	int st = sc.nextInt();
	int ed = sc.nextInt();
	list[st].add(ed);
	list[ed].add(st);
}
int cnt = 0;
BFS(1,0);

간선의 개수만큼 for문을 돌면서 시작 정점, 도착 정점을 입력받았다.

list[st].add(ed)를 하면 시작 정점을 번호로 가지는 배열 안에다가 도착 정점을 리스트에 때려 박는 것이다.

1,4 / 1,5 / 1,6이 주어진다면 1번 배열에다가 4,5,6이라는 도착 정점 정보를 리스트로 넣은 것.

무방향이기 때문에 반대로도 넣어준다.

 

몇 번 BFS를 동작했는지 확인하기 위해 cnt 변수를 넣고 BFS를 돌린다.

 

public static void BFS(int depth, int cnt) {
		q.add(depth);
		visited[depth] = true;
		while(!q.isEmpty()) {
			int curr = q.poll();
			for(int i=0; i<list[curr].size(); i++) {
				int temp = list[curr].get(i);
				if(!visited[temp]) {
					visited[temp] = true;
					q.add(temp);
					cnt++;
				}
			}
		}
		System.out.println(cnt);
	}

우선 큐에 몇 번째부터 시작할지 depth를 넣어준다.(1번부터 시작하므로 1을 넣게 된다.)

그리고 visited에 해당 번호를 true로 만들어준다.

 

이제 반복을 도는데 큐가 비어있지 않으면 실행하도록 한다.

우선 curr에 큐를 빼서 현재 정점 정보를 저장한다. (curr에는 1을 넣었으니 1이 들어있다.)

for문을 도는데 list[curr].size() 만큼 반복을 돌게 된다.

 

현재 curr은 1이니 list[1].size()랑 같다고 생각하자.

만약에 입력으로 1,4 / 1,5 / 1,6이 들어온다고 하면 list[1].size()를 뽑아내면 3이 나오게 된다.

즉 curr번 정점에서 출발하는 간선의 개수만큼 돈다고 생각하면 된다.

 

temp변수에 list[curr].get(i)를 집어넣어 준다. (위에 예시대로 하면 temp는 4가 들어간다)

만약에 temp번이 방문하지 않았다면 true로 만들고

큐에 temp를 넣어준다.(4번에서 출발하는 간선이 있다면 계속 돌 거다)

이후 cnt++을 해주고 마지막에 cnt를 출력해 준다.