[백준/java] 2606번: 바이러스 - 인접행렬을 이용한 bfs 풀이 문제

2606번: 바이러스

 

728x90

이번 포스팅은 오랜 만에 알고리즘 문제를 올려봅니다.

 

그동안 할줄 몰라서 안풀었던 인접행렬을 이용하는 문제인

 

반응형

 

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

2606번: 바이러스

 

백준 2606번 바이러스 문제를 풀어보도록 하겠습니다.

 

 

백준 2606번 바이러스

이 문제를 이해하고 풀기 위해서는 인접행렬을 이용해야 합니다.

 

인접행렬이란?

인접행렬

위키백과, 우리 모두의 백과사전.

그래프 이론에서, 인접 행렬(adjacency matrix)은 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각 행렬이다.

 

으로 정의되어 있다.

 

다시 말해, 위 그림과 같은 그래프를 행렬로 표현하는 것이 인접행렬이다.

 

위의 그림을 인접행렬로 표현하면 다음과 같다.

 

백준 2606 바이러스 인접행렬로 표현

 

코드로 구현시, 

입력값이 

1 2 일때,

 

matrix[1][2] = 1;

matrix[2][1] = 1; 

 

이렇게 해주어야 인접행렬을 만들 수 있다. 

 

이렇게 인접행렬로 구현한 후, 

 

BFS로 탐색을 하는데, 방문했던 노드에 대해서 카운트 하지 않아야 하고,

 

1에서부터 출발해서 감염된 컴퓨터의 갯수를 구해야하니 1은 제외하고 카운트를 해야한다.

 

package dfsAndBfs;

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

public class P2606_Virus {
	static int[][] map;			// 인접행렬을 만들기 위한 변수
	static boolean[] visit;		// 방문한 컴퓨터를 체크하기 위한 로직
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int com = stoi(br.readLine());
		int line = stoi(br.readLine());
		
		map = new int[com][com];
		visit = new boolean[com];
		
		while(line-- > 0) {
			String[] spots = br.readLine().split(" ");
			int first = stoi(spots[0]) - 1;
			int second = stoi(spots[1]) - 1;
			
			map[first][second] = 1;
			map[second][first] = 1;
		}
		
		int idx = 0, cnt = 0;
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(idx);
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			
			for (int i = 0; i < map[cur].length; i++) {
				if(map[cur][i] == 1 && !visit[i]) {
					if(i != 0) cnt++;
					visit[i] = true;
					q.add(i);
				}
			}
		}
		
		System.out.println(cnt);
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
}