[BOJ 2606] 바이러스

popolarburr·2023년 4월 18일
0
post-thumbnail

- 문제




- 풀이


import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int twin = sc.nextInt();

        int[][] graph = new int[size + 1][size + 1];
        int[] check = new int[size + 1];
        Map<Integer, List<Integer>> map = new HashMap<>();

//        그래프 형성
        for (int i = 0; i < twin; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a][b] = graph[b][a] = 1;
        }

//        map에다가 해당하는 노드 연결
        for (int i = 1; i <= size; i++) {
            List<Integer> tmp = new ArrayList<>();
            for (int j = 1; j <= size; j++) {
                if (graph[i][j] == 1) {
                    tmp.add(j);
                }
            }
            map.put(i, tmp);
        }

        int count = dfs(map, check, 1, 0);
        System.out.println(count);
    }

    public static int dfs(Map<Integer, List<Integer>> map, int[] check, int node, int count) {
        check[node] = 1;
        for (int i : map.get(node)) {
            if (check[i] == 0) {
                count = dfs(map, check, i, count+1);
            }
        }
        return count;
    }
}

- 정리

이 문제는 DFS/BFS 및 그래프 문제를 풀어보기 위해 찾아서 푼 문제이다. 난생 처음으로 꽤나 어려운 문제를 풀어보기로 하고 풀었는데, 생각보다 쉽게 풀리다 막판가서 DFS구현에서 막혔다. 풀이는 이러하다.
문제 자체가 무방향 그래프를 제시해줌으로써, graph[a][b] = graph[b][a] = 1이라는 것을 캐치했다.
문제를 보면 방향성이 없기 때문에, 각 노드가 서로 연결되어있다고 보는 것이다. 이차원배열을 통해 graph를 구현하고, 이를 Map에다가 결과값을 담았다. MapMap<Integer, List<Integer>> 이다. 키는 각 노드를 의미하고, 밸류는 각 노드와 연결되어 있는 지점을 의미한다.

그렇게 map을 만들고나서 어떻게 구현하지 하다가 DFS가 떠올라서 DFS로 풀었다.

문제가 1번 컴퓨터에 바이러스가 발생했을 시, 몇 대의 컴퓨터가 동시에 바이러스가 발생하는지 찾는 것이기 때문에 각 노드들의 연결된 고리를 다 찾고 들어가야하기 때문에 DFS를 사용했다.


[출처] : 개인저장소

profile
차곡차곡

0개의 댓글