[Java] 백준 2606번 문제 (바이러스)

문제설명

 

소스코드

DFS풀이(스택)

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

public class Main
{
   static int N; //vertex
   static int M; //edge
   static int V; //첫 탐색
   static boolean visited[]; //방문 표시
   static int vertex[][]; //인접 행렬
   static int count = 0; //감염된 컴퓨터 수
   
   static void DFS(int V) //첫 탐색 위치를 매개변수로 받음
   {
	   Stack<Integer> stack = new Stack<>();
	   visited = new boolean[N + 1]; //(인덱스는 0부터 시작이므로 편의상 1추가)
	   stack.push(V);
	   while(!stack.empty()) //스택이 비어있지 않다면
	   {
		   int temp = stack.pop(); //스택에서 pop한 것을 임시로 저장
		   if(visited[temp] == true) continue; //이미 방문한 곳이라면 pass
		   else //방문한 곳이 아니라면
		   {
			   visited[temp] = true; //방문했다고 표시
			   ++count;
			   for(int j = 1; j < vertex[temp].length; ++j) //해당 행에 있는 모든 vertex를 검사
			   {
				   if(vertex[temp][j] == 1) stack.push(j); //두 노드가 간선으로 연결되어 있다면 스택에 push
			   }
		   }
	   }
	   System.out.println(--count); //1번 컴퓨터는 제외
   }
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine()); //vertex 수(정점 수)
		M = Integer.parseInt(br.readLine()); //edge 수(간선 수)
		V = 1; //첫 탐색을 어디로 하는지 
		vertex = new int[N + 1][N + 1]; //인접 행렬 (인덱스는 0부터 시작이므로 편의상 1추가)
		for(int i = 1; i <= M; ++i) //간선의 수 만큼 입력을 받음
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			int row = Integer.parseInt(st.nextToken());
			int col = Integer.parseInt(st.nextToken());
			vertex[row][col] = 1; //무방향 그래프는 대칭 행렬이므로
			vertex[col][row] = 1; //무방향 그래프는 대칭 행렬이므로
		}
		DFS(V);
	}
}

 

BFS풀이(큐)

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

public class Main
{
   static int N; //vertex
   static int M; //edge
   static int V; //첫 탐색
   static boolean visited[]; //방문 표시
   static int vertex[][]; //인접 행렬
   static int count = 0; //감염된 컴퓨터 수
   
   static void BFS(int V) //첫 탐색 위치를 매개변수로 받음
   {
	   Queue<Integer> queue = new LinkedList<>();
	   visited = new boolean[N + 1]; //(인덱스는 0부터 시작이므로 편의상 1추가)
	   queue.offer(V);
	   while(!queue.isEmpty()) //큐가 비어있지 않다면
	   {
		   int temp = queue.poll(); //큐에서 dequeue 한 것을 임시로 저장
		   if(visited[temp] == true) continue; //이미 방문한 곳이라면 pass
		   else //방문한 곳이 아니라면
		   {
			   ++count;
			   visited[temp] = true; //방문했다고 표시
			   for(int j = 1; j < vertex[temp].length; ++j) //해당 행에 있는 모든 vertex를 검사
			   {
				   if(vertex[temp][j] == 1) queue.offer(j); //두 노드가 간선으로 연결되어 있다면 큐에 enqueue
			   }
		   }
	   }
	   System.out.println(--count); //1번 컴퓨터는 제외
   }
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine()); //vertex 수(정점 수)
		M = Integer.parseInt(br.readLine()); //edge 수(간선 수)
		V = 1; //첫 탐색을 어디로 하는지 
		vertex = new int[N + 1][N + 1]; //인접 행렬 (인덱스는 0부터 시작이므로 편의상 1추가)
		for(int i = 1; i <= M; ++i) //간선의 수 만큼 입력을 받음
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			int row = Integer.parseInt(st.nextToken());
			int col = Integer.parseInt(st.nextToken());
			vertex[row][col] = 1; //무방향 그래프는 대칭 행렬이므로
			vertex[col][row] = 1; //무방향 그래프는 대칭 행렬이므로
		}
		BFS(V);
	}
}

설명

• 주석 참고
• 아래의 문제에 사용했던 코드를 재사용했음

2023.11.17 - [백준] - [Java] 백준 1260번 문제 (DFS와 BFS)

[Java] 백준 1260번 문제 (DFS와 BFS)