[DFS] 웜 바이러스

웜 바이러스←link(Click)

$문제$ $설명$

이 코드는 “웜 바이러스” 문제와 유사한 형태의 그래프 탐색 문제를 다룬다.

• 1번 컴퓨터가 바이러스에 감염되었을 때,
• 연결된 네트워크를 통해 감염될 수 있는 다른 컴퓨터의 수를 구하는 문제이다.

즉, 1번 노드에서 시작해 DFS로 모든 연결된 노드를 탐색하며,

감염된 컴퓨터(= 방문한 노드)의 수를 세는 로직이다.

---

$코드$

package com.lhw.section02.searching;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.StringReader;
import java.util.Stack;
import java.util.StringTokenizer;

/*
 * 깊이 우선 탐색(Depth-First Search)
 * 후입선출 구조의 stack을 활용하거나 재귀호출을 이용한다.
 * 시작 노드에서 출발해 한 방향으로 갈 수 있는 만큼 깊이 탐색한 후,
 * 더 이상 진행할 수 없을 때 이전 분기점으로 돌아가 다른 경로를 탐색하는 알고리즘이다.
 */
public class A_DFS {

    static int node, edge;        // 노드 수, 간선 수
    static int[][] map;           // 그래프 연결 정보를 저장하는 2차원 배열
    static boolean[] visit;       // 방문 여부 체크 배열
    static int count = 0;         // 감염된 컴퓨터 수

    public static Integer solution(String input) throws IOException {
        BufferedReader br = new BufferedReader(new StringReader(input));

        node = Integer.parseInt(br.readLine()); // 전체 노드 수 (예: 7)
        edge = Integer.parseInt(br.readLine()); // 간선 수 (예: 6)

        // 인접 행렬 생성 (1번부터 사용하기 위해 node+1 크기로 생성)
        map = new int[node + 1][node + 1];
        visit = new boolean[node + 1];

        StringTokenizer st;

        // 간선 정보 입력
        for (int i = 0; i < edge; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            // 무방향 그래프이므로 양쪽 모두 연결 표시
            map[a][b] = map[b][a] = 1;
        }
		// 1번 노드에서 탐색 시작
        dfsStack(1); // 스택 
        dfsRecursion(1); //재귀
        return count;
    }

---

$코드 구조$ $및$ $로직 해설$

1. 그래프 입력 및 초기화

map = new int[node + 1][node + 1];
visit = new boolean[node + 1];

• map은 인접 행렬(adjacency matrix) 형태로 그래프를 표현한다. 예를 들어, 1번과 2번이 연결되어 있다면 map[1][2] = map[2][1] = 1로 표시된다.
  
• visit[i]는 노드 i가 방문되었는지 여부를 나타낸다. 중복 방문을 막기 위해 반드시 필요하다.
  

---

2. 그래프 연결 정보 입력

for (int i = 0; i < edge; i++) {
    st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    map[a][b] = map[b][a] = 1;
}

• 각 간선 정보는 "a b" 형식으로 입력된다.
• 무방향 그래프이므로 양쪽 모두 연결 표시가 필요하다.
• 예를 들어 입력이 아래와 같다면:

7
6
1 2
2 3
1 5
5 2
5 6
4 7

이때 map 배열에는 다음과 같은 연결 상태가 저장된다.

노드	연결된 노드
1	2, 5
2	1, 3, 5
3	2
4	7
5	1, 2, 6
6	5
7	4

---

$DFS$ - $Stack$

private static void dfsStack(int start) {
    // 방마다 들어갔는지 체크해주는 영역
    Stack<Integer> stack = new Stack<>();
    stack.push(start); // start값을 stack에 처음으로 넣어준다.
    visit[start]  = true; //여기까지가 탐색PDF 24page
    while (!stack.isEmpty()) {
        int current = stack.pop();
        for (int i = 1; i<=node; i++) {
            /*그래프 그리드에 1번(vertex가 있는 곳)이고, 방문하지 않았다면*/
            if(map[current][i] == 1 && !visit[i]){
                stack.push(i);
                visit[i] = true;
                count++;
            }
        }
    }
}

DFS(스택) 탐색 로직

Stack<Integer> stack = new Stack<>();
stack.push(start);
visit[start] = true;

• DFS의 시작점인 start 노드를 스택에 추가한다.
• 바로 방문 처리(visit[start] = true)를 해 중복 추가를 방지한다.

---

스택을 이용한 탐색

while (!stack.isEmpty()) {
    int current = stack.pop();
    for (int i = 1; i <= node; i++) {
        if (map[current][i] == 1 && !visit[i]) {
            stack.push(i);
            visit[i] = true;
            count++;
        }
    }
}

• 스택이 빌 때까지 반복한다.
• pop()으로 현재 노드를 꺼내고, 그 노드와 연결된 다른 노드를 찾는다.
• 연결되어 있고(map[current][i] == 1), 아직 방문하지 않았다면:
  • push()로 스택에 넣고
  • visit[i] = true로 방문 처리
  • 감염된 컴퓨터 수(count)를 하나 늘린다.

---

$실행 흐름 예시$

입력 예시

7
6
1 2
2 3
1 5
5 2
5 6
4 7

탐색 순서 흐름

1. 시작: 1번 → 스택 [1]
2. 1 꺼냄 → 연결된 2, 5 push → 스택 [2, 5]
3. 5 꺼냄 → 연결된 2, 6 push(2는 이미 방문) → [2, 6]
4. 6 꺼냄 → 연결된 5 이미 방문 → [2]
5. 2 꺼냄 → 연결된 1, 3, 5 중 3만 미방문 → push(3) → [3]
6. 3 꺼냄 → 연결된 2 이미 방문 → 스택 비어있음 → 탐색 종료

감염된 노드: 2, 3, 5, 6

총 감염 수: 4

따라서 count = 4가 반환된다.

---

$DFS$ - $Recursion$

public static void dfsRecursive(int start) {
    /*해당 노드를 방문했으므로 방문 배열에 표기*/
    visit[start] = true;
    /*start 노드의 이웃을 탐색하는 과정*/
    for (int i = 1; i<=node; i++) {
        /*start 정점의 이웃 중 방문하지 않은 이웃을 찾는다.*/
        if (map[start][i] == 1 && !visit[i]) {
            /*바이러스를 전파알 이웃 노드 컴퓨터를 찾은 것이므로
            * count를 증가시키고 해당 이웃 노드를 방문해서 다시 이웃노드를
            * 재귀적으로 탐색한다.
            * */
            count++;
            dfsRecursive(i);
        }
    }
}