백준 알고리즘: 2606번 바이러스

문제 정보

---

 

2606번: 바이러스

 

핵심

---

그래프 탐색 알고리즘을 통해서 연결된 노드를 탐색하는 것!

여러 그래프 탐색 알고리즘을 사용할 수 있겠지만, 나는 깊이 우선 탐색을 사용하여 풀이하였다

map을 어떻게 입력 받고 구성할 것이며 visited를 확인해주는 것이 매우 중요하다

하지만 그렇게 어렵지는 않았던 것 같다

 

풀이

---

package solving;

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        List<List<Integer>> map = new ArrayList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int numberOfComputers = Integer.parseInt(br.readLine());
        for (int i = 0; i <= numberOfComputers; i++) {
            map.add(new LinkedList<>());
        }
        boolean[] visited = new boolean[numberOfComputers + 1];
        int numberOfEdges = Integer.parseInt(br.readLine());
        for (int i = 0; i < numberOfEdges; i++) {
            String[] splitStr = br.readLine().split(" ");
            int computer1 = Integer.parseInt(splitStr[0]);
            int computer2 = Integer.parseInt(splitStr[1]);
            map.get(computer1).add(computer2);
            map.get(computer2).add(computer1);
        }
        dfs(1, map, visited);
        System.out.println(result);
    }

    static int result = 0;

    public static void dfs(int currentNode, List<List<Integer>> map, boolean[] visited) {
        if (visited[currentNode])
            return;
        List<Integer> linkedNodes = map.get(currentNode);
        visited[currentNode] = true;
        result = currentNode == 1 ? result : result + 1;

        while (!linkedNodes.isEmpty()) {
            int linkedNode = linkedNodes.remove(0);
            if (!visited[linkedNode])
                dfs(linkedNode, map, visited);
        }
    }
}

여기서, 해당 노드를 방문했는지 확인하는 부분이 두 군데가 존재하는데

if (visited[currentNode])
    return;
List<Integer> linkedNodes = map.get(currentNode);
visited[currentNode] = true;
result = currentNode == 1 ? result : result + 1;

while (!linkedNodes.isEmpty()) {
    int linkedNode = linkedNodes.remove(0);
    dfs(linkedNode, map, visited);
}

처음에는 위와 같이 방문했는지 여부와 상관 없이, 무조건 Recursive Call을 한 후 해당 함수의 첫 줄에서 확인하고 return하도록 코드를 작성하였는데

if (visited[currentNode])
    return;
List<Integer> linkedNodes = map.get(currentNode);
visited[currentNode] = true;
result = currentNode == 1 ? result : result + 1;

while (!linkedNodes.isEmpty()) {
    int linkedNode = linkedNodes.remove(0);
    if (!visited[linkedNode])
        dfs(linkedNode, map, visited);
}

위와 같이 call하기 전에 방문했는지 확인하는 작업을 통하여 입력의 개수가 작은 경우 그렇게 유의미하지는 않지만 많아지면 Call Stack의 수를 줄여 주어 도움을 줄 것으로 예상한다!

 

Source Code on GitHub

---