[알고리즘 PS] 백준 2468번 안전 영역 자바 문제풀이

문제

해당 포스팅은 백준의 2468번 안전 영역 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

2468번: 안전 영역

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이번 문제는 BFS, DFS 모두 사용할 수 있는 문제이다.

 

강수량을 1부터 원소의 최대까지 각각 조사하는 방법을 취하면 된다.

 

정답 코드

public class Main {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] nm = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);
        visited = new boolean[n + 1];
        for(int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        while(m-- > 0) {
            String[] uv = br.readLine().split(" ");
            int u = Integer.parseInt(uv[0]);
            int v = Integer.parseInt(uv[1]);

            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            if(dfsByRecursive(i)) {
                answer += 1;
            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }

    private static boolean dfsByRecursive(int x) {
        if(visited[x]) {
            return false;
        }else {
            visited[x] = true;
            int size = graph.get(x).size();
            for (int i = 0; i < size; i++) {
                int value = graph.get(x).get(i);
                if(!visited[value]){
                    dfsByRecursive(value);
                }
            }
            return true;
        }
    }

    private static boolean bfs(int x) {
        Queue<Integer> queue = new LinkedList<>();

        if(visited[x]) {
            return false;
        }else {
            queue.add(x);
            visited[x] = true;

            while(!queue.isEmpty()) {
                x = queue.remove();
                int size = graph.get(x).size();
                for(int i = 0; i < size; i++) {
                    int value = graph.get(x).get(i);
                    if(!visited[value]) {
                        queue.add(value);
                        visited[value] = true;
                    }
                }
            }
            return true;
        }
    }
}

 

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

로그인