#2606 : 바이러스

풀이방법

사용된 것:

ArrayList

DFS(깊이우선탐색)

BFS(너비우선탐색)

 

2022.02.08

깊이우선탐색 방식으로 1번 컴퓨터와 연결된 모든 컴퓨터를 방문하고,

새로운 컴퓨터를 방문할 때마다 초기값이 0인 int 변수 count를 1씩 증가시켰다.

 

깊이우선탐색에는 재귀함수를 사용하였다.

 

그래프의 표현에는 인접리스트 방식을 사용하였다.

 

모든 간선이 무방향이기 때문에, 서로 연결된 두 노드의 리스트에 모두 서로를 추가하였다.

예를 들어 3과 5가 연결되어있다면

3번 리스트에도 5를 추가하고, 5번 리스트에도 3을 추가하는 식이다.

 

 

2022.06.01

너비우선탐색 방식의 코드를 추가해주는 김에, 조금 더 정리한 깊이우선탐색 코드도 추가했다.

 

 

아래부터 위 순으로 2월 DFS 코드, 6월 DFS 코드, 6월 BFS 코드

 

코드

Java(2022.02.08) 첫 DFS 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static ArrayList<Integer>[] a;	//노드 및 간선정보 배열
	static boolean[] visited;	//방문여부 체크
	static int n, m;	//노드 수, 간선 수
	static int count;	//출력할 결과값
	
	static int dfs(int i) {	//count 값을 계산하여 리턴하는 함수.
		visited[i] = true;
		for(int k : a[i]) {
			if(visited[k] == false) {
				count++;
				dfs(k);
			}
		}
		return count;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		//n과 m 읽어오기
		n = sc.nextInt();
		m = sc.nextInt();

		//visited 선언
		visited = new boolean[n+1];
		//a 선언
		a = new ArrayList[n+1];
		for(int i = 0; i<=n; i++) {
			a[i] = new ArrayList<Integer>();
		}
		
		for(int i = 0 ; i<m; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			a[x].add(y);
			a[y].add(x);
		}
		
		count = 0;
		
		System.out.print(dfs(1));
		
		sc.close();

	}

}

 

Java(2022.06.01) 조금 더 정리해서 짠 DFS 코드

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

public class Main {
	
	static ArrayList<Integer>[] arr;	//간선 정보 저장용 배열
	static boolean[] visited;
	static int cnt;
	
	static void dfs(int cur) {
		if(visited[cur]) return;
		
		visited[cur] = true;
		cnt++;
		
		for(int i: arr[cur]) dfs(i);
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//컴퓨터의 수와 연결의 수 읽어오기
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		//간선정보 읽어와 저장하기
		arr = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) arr[i] = new ArrayList<Integer>();
		for(int i=0; i<m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a].add(b);
			arr[b].add(a);
		}
		//깊이우선탐색 하기
		cnt = -1;	//자신은 제외하고 세어야 하므로 -1로 초기화
		visited = new boolean[n+1];
		dfs(1);
		
		//정답 출력하기
		System.out.print(cnt);

	}

}

 

Java(2022.06.01) BFS 방식의 풀이코드

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 Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//컴퓨터의 수와 연결의 수 읽어오기
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		//간선정보 읽어와 저장하기
		ArrayList<Integer>[] arr = new ArrayList[n+1];	//여기에 저장
		for(int i=1; i<n+1; i++) arr[i] = new ArrayList<Integer>();
		for(int i=0; i<m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a].add(b);
			arr[b].add(a);
		}
		//너비우선탐색 하기
		boolean[] visited = new boolean[n+1];
		int cnt = -1;	//자신은 제외하고 세어야 하므로 -1로 초기화
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(1);
		while(!queue.isEmpty()) {
			if(visited[queue.peek()]) {queue.poll(); continue;}
			
			int cur = queue.poll();
			visited[cur] = true;
			cnt++;
			for(int i: arr[cur]) queue.add(i);
		}

		//정답 출력하기
		System.out.print(cnt);

	}

}