[백준] 단계별로 풀어보기(단계:24, DFS와BFS,JAVA)2606번, 바이러스

문제 링크

2606번: 바이러스

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

DFS(깊이 우선 탐색)은 아래 그림처럼 어떤 조건을 가지고 목표노드에 도달하기까지 자식노드를 통해 이동하며 목표노드까지 도달하는 것을 말합니다.

자식 노드에 도착하면 그 자식노드에서 조건에 만족하는 자식노드로 다시 이동하여 목표 노드로 이동합니다.

 

출처 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

DFS

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

BFS

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

이 문제에 핵심은

1. 시작 정점은 항상 1부터 시작한다.

2. 1~N까지의 정점이 만들어진다.

3. 감염된 컴퓨터의 개수를 구할 때 1번 컴퓨터는 제외한다.

 

정점은 1~N까지의 정점이 생성된다고 문제에 표현되기 때문에 정점(컴퓨터)의 연결을 표현하는 2차원 배열을 만들었습니다.

computer[N+1][N+1]

computer[i][j]의 값은 정점(컴퓨터) i와 정점(컴퓨터) j가 인접하고 있으면 1, 없으면 0을 저장하였습니다.

만약 정점(컴퓨터) 2와 정점(컴퓨터) 1이 인접하고 있다면

computer[2][1], computer[1][2]가 인접하다는 것을 표현하는 배열의 값이기 때문에 computer[2][1] = 1, computer[1][2] =1로 저장한다.

 

dfs를 구하는 것은 재귀를 사용하여 해결하였습니다.

저는 for문을 1부터 시작하여 낮은 값을 먼저 탐색하도록 하였습니다.

check배열을 통해서 해당 정점을 탐색했는지를 확인을 통해서 탐색하였습니다.

예제 입력1에서

시작정점이 1로 표현되었기 때문에

정점 1에서 인접한 정점는 2, 5입니다.

낮은 값 정점 2를 탐색합니다.

정점 1 -> 정점 2

 

정점 2에서 인접한 정점는 1, 3, 5입니다.

낮은 값을 탐색해야 해서 1을 탐색하려고 하면 1은 시작정점로 벌써 탐색되었기 때문에 3를 탐색합니다.

정점 2 -> 정점 3

 

정점 3에서 인접한 정점는 2입니다.

2는 탐색되었기 때문에 현재 깊이에서 탐색을 종료합니다.

 

이제 다시 시작 정점 1로 가서 탐색을 진행합니다. 인접한 정점은 2, 5 입니다.

낮은 값을 2을 탐색하려고 하면 2는 탐색되었기 때문에 5를 탐색합니다.

정점 1 -> 정점 5

 

정점 5에서 인접한 정점는 1, 2, 6입니다.

낮은 값을 1, 2을 탐색하려고 하면 1, 2은 탐색되었기 때문에 6을 탐색합니다.

정점 5 -> 정점 6

 

정점 6에서 인접한 정점는 5입니다.

5는 탐색되었기 때문에 현재 깊이에서 탐색을 종료합니다.

 

다시 시작 정점 1로 가서 탐색을 진행합니다. 인접한 정점은 2, 5 입니다.

2, 5을 모두 탐색되었기 때문에 탐색을 종료합니다.

 

결과적으로 탐색한 순서는

정점 1 -> 정점 2 -> 정점 3 -> 정점 5 -> 정점 6 이 됩니다.

 

결과적으로 시작 정점(컴퓨터)을 제외한 감염된 컴퓨터는 2, 3, 5, 6으로써 4가 결과로 출력됩니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. computer[N+1][N+1] 과 check[N+1]로 정점(컴퓨터)의 개수만큼 초기화해줍니다.

2. 입력값을 받아서 computer에서 i와 j가 인접하면 1을 인접하지 않으면 0으로 저장하였습니다.

3. DFS(깊이 우선 탐색)를 재귀문을 사용하여 탐색 순서를 구하였습니다.

4. DFS에서 시작 컴퓨터를 제외한 방문한 컴퓨터들의 개수를 결과로 출력하였습니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 computer배열을 초기화해주었습니다.
• DFS을 통해 감염된 컴퓨터의 개수를 구하는 dfs 함수를 만들었습니다.
• BufferedWriter에 시작 컴퓨터를 제외한 감염된 컴퓨터의 개수를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• dfs은 check[], computer[][]와 재귀 및 count를 통해 감염된 컴퓨터를 탐색하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int[][] computer;	//컴퓨터 인접 저장 배열
	public static boolean[] check;	//컴퓨터 탐색했는지 확인 배열
	public static int N,M,count = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //--------입력값 저장 및 배열 초기화---------
    	StringTokenizer st;
    	N = Integer.parseInt(br.readLine());
    	M = Integer.parseInt(br.readLine());
    	computer = new int[N+1][N+1];
    	check = new boolean[N+1];
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		int s = Integer.parseInt(st.nextToken());
    		int e = Integer.parseInt(st.nextToken());
    		computer[s][e] = 1;
    		computer[e][s] = 1;
    	}
    	dfs(1);		//깊이 우선 탐색 함수 실행
    	bw.write(count-1 + "\n");	//감염된 컴퓨터 개수 BufferedWriter 저장
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();
    }
    //------깊이 우선 탐색으로 감염된 컴퓨터 구하는 함수-------
    public static void dfs(int cur) {
    	check[cur] = true;		//탐색 완료
    	count++;		// 감염된 컴퓨터 개수 증가
    	for(int i=1;i<=N;i++) {
    		if(!check[i] && computer[cur][i]==1) {	//탐색하지 않았고 인접하면
    			dfs(i);
    		}
    	}
    }
}