[BOJ] 2606. 바이러스

BaekJoon 2606. 바이러스

* 문제의 저작권은 BOJ 및 문제를 만든 사람에게 있습니다.

 

 

 

 

 

 

[문제 접근]

 

컴퓨터 대수만큼 배열을 만들어 각 컴퓨터 번호들이 연결되어있으면 1 연결되어있지 않으면 0으로 값을 줬다.

1번 컴퓨터가 바이러스에 걸린 컴퓨터라서 queue와 dfs에 바로 1을 넣어줬다.

방문하지 않았고 연결된 컴퓨터의 좌표 값이 1이라면 바이러스에 걸린 컴퓨터이기 때문에 answer++ 해줌

 

 

 

 

 

 

 

 

[코드]

 

<DFS>

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

public class Main {
	static boolean[] visited;
	static int answer;
	static int computer;
	static int[][] map;
	
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		computer = Integer.parseInt(br.readLine());
		int connect = Integer.parseInt(br.readLine());
		map = new int[computer+1][computer+1];
		visited = new boolean[computer+1];
		
		for (int i = 0; i < connect; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			map[x][y] = map[y][x] = 1;
		}
		dfs(1);
		System.out.println(answer);
	}

	static void dfs(int num) {
		/* 방문했으면 넘김 */
		if (visited[num]) {
			return;
		}
		
		if (num>computer) {
			return;
		}
		
		visited[num] = true;
		for (int i = 1; i <= computer; i++) {
			if (map[num][i] == 1) {
				if (!visited[i]) {
					answer++;
					dfs(i);
				}
			}
		}
	}
}

 

 

<BFS>

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

public class Main {
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int computer = Integer.parseInt(br.readLine()); //컴퓨터 대수
		int connect = Integer.parseInt(br.readLine()); //연결된 컴퓨터 쌍
		int[][] map = new int[computer+1][computer+1];
		boolean[] visited = new boolean[computer+1];
		
		int answer = 0;
		
		for (int i = 0; i < connect; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			map[x][y] = map[y][x] = 1; // 1이면 연결된 컴퓨터
		}

		Queue<Integer> queue = new LinkedList<>();
		queue.add(1);
		
		while (!queue.isEmpty()) {
			int temp = queue.poll();
			visited[temp] = true;
			for (int i = 1; i <= computer; i++) {
				if (map[temp][i] == 1) {
					if (!visited[i]) {
						queue.offer(i);
						visited[i] = true;
						answer++;
					}
				}
			}
		}
		
		System.out.println(answer);
	}
}