문제
컴퓨터 N대가 네트워크로 연결되어 있다. 1번 컴퓨터가 바이러스에 걸리면 연결된 컴퓨터들도 모두 바이러스에 감염된다. 1번 컴퓨터로 인해 감염되는 컴퓨터 수를 구하는 문제다.
입력
- 첫째 줄: 컴퓨터 수 N (1 ≤ N ≤ 100)
- 둘째 줄: 연결 쌍의 수 P
- 다음 P줄: 연결된 두 컴퓨터 번호
출력
1번 컴퓨터로 인해 바이러스에 걸리는 컴퓨터 수 (1번 제외)
예제
| 입력 | 출력 |
|---|---|
7 6 1 2 2 3 1 5 5 2 5 6 4 7 | 4 |
풀이
인접 행렬로 그래프를 표현하고, DFS로 1번 컴퓨터와 연결된 모든 컴퓨터를 탐색한다. 방문 배열로 중복 방문을 방지하며, 방문한 노드 수에서 1번 컴퓨터를 제외한 값이 정답이다.
- N×N 인접 행렬
arr을 선언하고, 연결 정보를 양방향으로 저장한다. dfs(1)로 1번 컴퓨터부터 탐색을 시작한다.- 이미 방문한 컴퓨터이면 즉시 반환한다.
- 현재 컴퓨터를 방문 처리하고
cnt를 증가시킨다. - 현재 컴퓨터와 연결된 모든 컴퓨터에 대해 재귀적으로 DFS를 호출한다.
- 초기
cnt = -1로 설정하여 1번 컴퓨터 자신을 제외한 감염 수를 출력한다.
핵심 아이디어: cnt를 -1로 초기화하여 탐색 시작점인 1번 컴퓨터를 자동으로 제외한다. 방문 배열의 조기 검사로 이미 방문한 노드를 즉시 반환하여 무한 루프를 방지한다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day39BOJ2606바이러스DFS재귀공부 { // 2606 바이러스 DFS공부
static int[][] arr;
static boolean[] check;
static int cnt = -1; // 감염된 pc수
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine()); // 컴퓨터 갯수
int P = Integer.parseInt(br.readLine()); // 간선의 수
arr = new int[N + 1][N + 1];
check = new boolean[N + 1];
for (int i = 0; i < P; i++) {
st = new StringTokenizer(br.readLine());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
arr[n1][n2] = arr[n2][n1] = 1;
}
// 완전탐색을 하는 방법에 어울림. ex) 미로의 출구 찾기
dfs(1);
System.out.println(cnt);
br.close();
}
private static void dfs(int idx) {
if (check[idx])// 이미 감염된 PC라면 돌아가라.
return;
check[idx] = true;
cnt++;
for (int i = 0; i < arr[idx].length; i++) {
// if (arr[idx][i] == 1 && !check[i]) { // return문이 있는데
if (arr[idx][i] == 1) { // !check[i] 이 필요할까?? 없어도 된다.
dfs(i);
}
}
}
}복잡도
- 시간: O(V^2) — 인접 행렬 기반 DFS, V는 컴퓨터 수
- 공간: O(V^2) — 인접 행렬 저장