[java 백준] 실버 2/11724번 연결요소의 개수

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

11724번: 연결 요소의 개수

import java.util.Scanner;
 
public class Main {
    public static int[][] arr;
 
    public static int[] visit;
    public static int count = 0;
 
    public static void dfs(int x) {
 
        if (visit[x] == 1) {
            return;
        } else {
            visit[x] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            if (arr[x][i] == 1 && visit[i] != 1) {
                dfs(i);
            }
        }
 
    }
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        int m = sc.nextInt();
        arr = new int[n + 1][n + 1];
        visit = new int[n + 1];
 
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            arr[u][v] = 1;
            arr[v][u] = 1;
        }
 
        for (int i = 1; i <= n; i++) {
            if (visit[i] == 0) {
                dfs(i);
                count++;
            }
        }
 
        System.out.println(count);
 
    }
}
 

 

그럴땐 1부터 n 까지 반복문을 돌린 후 visit[i]==0인 것들 중 가장 작은 i가 다시 dfs에 들어가는

 for (int i = 1; i <= n; i++) {

            if (visit[i] == 0) {

                dfs(i);

                count++;

            }

        }

--> 이 코드를 써주고 count ++ 해주면 되는 걸 

 

나는 bfs 메서드 안에서 for(int i:arr.get(x))를 해준후 (ArrayList로 풀었었다.)

만약 visit[i]==0 이 없다면 다시 1부터 visit.length까지 반복문을 돌려서 visit[i]==0 이면 bfs(i)를 해주는

큐와 재귀를 섞어버리는 이상한 짓을 했다.

그냥 메인메서드 안에 반복문 돌려주면 되는거였는데...

 

 

좀 더 효율적으로 문제를 푸는 것을 생각해봐야겠다. (정말 바보다. 생각이 없다.ㅜ)