https://www.acmicpc.net/problem/2606
백준 2606번: 바이러스 (Java) - DFS & ArrayList로 그래프 구현하기
📌 문제 개요
1번 컴퓨터가 바이러스에 걸렸다.
직접 연결된 컴퓨터를 통해 감염이 퍼질 수 있다.
감염된 컴퓨터의 총 수를 구하자. (단, 1번은 감염됐지만 제외)
💡 문제 유형
- 그래프 탐색
- DFS(깊이 우선 탐색)
- 인접 리스트 방식으로 그래프 구현
🧠 핵심 개념 정리
✅ 그래프(Graph)
- 정점(Node)과 간선(Edge)으로 이루어진 자료구조
- 이 문제에선 컴퓨터 = 정점, 연결 = 간선
✅ DFS (Depth-First Search)
- 깊이 우선 탐색
- 한 방향으로 계속 탐색하다가 더 이상 갈 곳이 없으면 되돌아감
- 재귀(Recursive) 방식으로 구현 가능
✅ 인접 리스트 (Adjacency List)
- 정점을 배열로 선언하고, 각 인덱스에 연결된 노드들을 리스트로 저장
- 자바에서는 ArrayList<ArrayList<Integer>> 형태로 구성
💻 코드 설명 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static boolean[] visited;
static ArrayList<ArrayList<Integer>> graph;
static int cnt = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine()); // 컴퓨터 수
M = Integer.parseInt(br.readLine()); // 연결 수
visited = new boolean[N + 1]; // 방문 배열
graph = new ArrayList<>();
// 인접 리스트 초기화
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
// 간선 정보 입력
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph.get(a).add(b); // 양방향 연결
graph.get(b).add(a);
}
DFS(1); // 1번 컴퓨터에서 시작
System.out.println(cnt - 1); // 자기 자신 제외
}
// DFS 함수
static void DFS(int V) {
visited[V] = true;
cnt++;
for (int next : graph.get(V)) {
if (!visited[next]) {
DFS(next);
}
}
}
}🧩 코드 분석 포인트
구문설명
| graph = new ArrayList<>(); | 전체 그래프 초기화 |
| graph.add(new ArrayList<>()); | 각 정점에 대한 연결 리스트 초기화 |
| DFS(int V) | 깊이 우선 탐색 함수 |
| visited[] | 중복 방문 방지용 boolean 배열 |
| cnt - 1 | 감염된 컴퓨터 수에서 1번 제외 |
📝 마무리 정리
- DFS는 연결된 모든 노드를 빠짐없이 탐색하는 데 유용
- ArrayList를 이용한 인접 리스트 구성은 메모리 효율적
- 1번 컴퓨터를 기준으로 연결된 컴퓨터를 모두 탐색 후, 개수만 세면 해결
'프로그래밍 & IT > Algorithm' 카테고리의 다른 글
| [알고리즘] 프로그래머스 가장 먼 노드 (0) | 2023.05.31 |
|---|---|
| [알고리즘] 프로그래머스 최솟값 만들기 (0) | 2023.05.31 |
| [알고리즘] 프로그래머스 최댓값과 최솟값 (0) | 2023.05.30 |
| [알고리즘] 프로그래머스 영어 끝말잇기 (2) | 2023.05.29 |
| [알고리즘] 프로그래머스 올바른 괄호 (0) | 2023.05.29 |