[백준](Java) 11724 - 연결 요소의 개수

문제링크

https://www.acmicpc.net/problem/11724

문제풀이

조건 체크를 안해서 시간초과가 떴다. 그래서 3시간을 날렸다...
연결 요소가
1 5
1 3
5 6
3 4
처럼 있다는 가정하게 bfs(1)부터 시작하여
map[1][1]~map[1][n]까지 돌아 조건에 맞는값을 queue에 넣고
넣은값 n으로 다시 요소들을 검색하는 방법을 생각했다.
1 -> 5,3 저장
5 -> 6 저장
3 -> 4 저장
6 탐색, 4 탐색..
1 3 4 5 6 을 한 요소로 묶고 방문했다는 표시를 남겨
다른 요소에서 1,3,4,5,6을 접근할수 없도록 했다.

문제를 풀기전에 chk를 2차원 배열로 만들었었다.
하지만 위의 logic을 구현하기 위해서는 각 번호의 방문값만 체크하면 된다고 생각했기에
1차원 배열로 수정했다.

만약에 map[i][j]에서 i를 이미 방문한적이 있다면 다시 탐색을 할 필요가 없으므로
방문한적이 없을때 bfs를 돈다.

     for (int i = 1; i <=n; i++) {
            if(!chk[i]){
                bfs(i);
            }
        }

bfs들어왔다는것은 하나의 연결요소라는 뜻이므로 answer++를 해준다.
이값을 queue에 넣고 그 배열에 가로 값들을 탐색해서 방문한적이 없고, 조건에 맞으면 queue에 넣고 해당 값은 true로 바꿔준다.

    public static void bfs(int y) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(y);
        answer++;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            chk[now] = true;
            for (int i =1; i <=n; i++) {
                if (!chk[i] && map[now][i] == 1 ) {
                    queue.add(i);
                    chk[i] = true;
                }
            }
        }
    }

코드

import java.util.*;

public class Main {

    static int n;
    static int m;
    static int[][] map;
    static boolean[] chk;
    static int answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n+1][n+1];
        chk = new boolean[n+1];

        for (int i = 0; i < m; i++) {
            int y = sc.nextInt();
            int x = sc.nextInt();
            map[y][x] = 1;
            map[x][y] = 1;
        }
        for (int i = 1; i <=n; i++) {
            if(!chk[i]){
                bfs(i);
            }
        }

        System.out.println(answer);
    }

    public static void bfs(int y) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(y);
        answer++;

        while (!queue.isEmpty()) {
            int now = queue.poll();
            chk[now] = true;
            for (int i =1; i <=n; i++) {
                if (!chk[i] && map[now][i] == 1 ) {
                    queue.add(i);
                    chk[i] = true;
                }
            }
        }
    }

}