[백준 / 2606] 바이러스 - JAVA

[백준 / 2606] 바이러스 - JAVA

DFS의 전형적인 문제라고 생각하며 그래프 이론을 빠삭하게 공부할 수 있는 문제라고 생각합니다.

그래프와 DFS에 대해 조금이라도 알고 싶고, 기초적인 문제를 푸시고 싶다면 이 문제를 푸시는 것을 추천드립니다.

자바로 풀었기에 둘이 연결되어 있는 vertex는 node라는 이차원 배열을 사용합니다.

또한 visit이라는 1차원 배열을 사용하여 해당 노드를 방문했는지를 알아봅니다.

n은 vertex 즉 node의 수, m은 edge 즉 연결 되어 있는 수입니다.

public class S3_2606 { static int[][] node; static boolean[] visit; static int n,m; static int result = 0; public static void main(String[] args)throws IOException{ Scanner sc = new Scanner(System.in); n = sc.nextInt(); //7 m = sc.nextInt(); //6 node = new int[n+1][n+1]; visit = new boolean[n+1]; int num1, num2; for(int i=0;i

우선 undirected graph이므로 node[num1][num2] 와 node[num2][num1]을 같은 1로 초기화 해줍니다.

만약 directed graph라면 한쪽만 해줘야합니다!

둘이 연결되어 있다면 그 숫자는 1로 만들어 놓고 시작합니다.

그 후 dfs를 돌립니다.

우선 매개변수로 들어온 숫자의 visit을 true로 만든 후 시작합니다.

그 후 재귀를 돌려줍니다.

만약 해당 노드가 1이고 (해당 노드가 연결) 만약 visit이 false라면 result를 1 더해주고 다시 그 dfs를 매개변수로 줍니다.

그렇게 무한히 하다보면 끝나게 되며 결과가 나오게 됩니다.

추가) 지속적으로 제가 n+1로 크기를 잡아놨는데 그 이유는 해당 문제의 요구사항 때문입니다. 배열이 0으로 시작하면 안되는데 문제의 요구사항은 0이 없고 시작이 1이라 그렇습니다. 그래서 n을 1씩 더해주고 시작하게 됩니다.

만약 0부터 시작한다면 그건 굳이 n+1 로 시작하지 않아도 되겠습니다.

from http://soobinhand.tistory.com/32 by ccl(A) rewrite - 2021-10-27 01:00:33