[java]창용 마을 무리의 개수 - SWEA 7465

풀이

문제 해석을 하자면,

• 주어진 두사람 간의 관계들을 이용하여 총 무리의 개수를 구하자.

풀이

• 단순 구현으로 풀려다가 2시간을 날린 문제… ㅜㅜ
• 간단히 완전탐색(dfs)+visited(방문) 으로 해결이 된 문제였다…

코드

public static int result; // 무리 개수

public static void dfs(int idx, boolean[] visited, List<Integer>[] inArr) {
    List<Integer> inNum = inArr[idx];
    for(int num : inNum) {
        if(visited[num]) continue;
        visited[num] = true;
        dfs(num, visited, inArr);
    }
}

public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int T = Integer.parseInt(br.readLine());
    for(int t=1; t<=T; t++) {
        //init
        result=0;
        //input
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(stk.nextToken());
        int M = Integer.parseInt(stk.nextToken());
        boolean[] visited = new boolean[N+1]; // 매번 할당
        List<Integer>[] inArr = new ArrayList[N+1]; // 매번 할당
        for(int i=0; i<N+1; i++) inArr[i] = new ArrayList<>(); // 초기화
        for(int i=0; i<M; i++) {
            stk = new StringTokenizer(br.readLine(), " ");
            int n1 = Integer.parseInt(stk.nextToken());
            int n2 = Integer.parseInt(stk.nextToken());
            inArr[n1].add(n2);
            inArr[n2].add(n1); // 양방향 간선
        }
        //run
        for(int i=1; i<=N; i++) {
            if(visited[i]) continue; 
            dfs(i, visited, inArr);
            result++; // 이곳까지 오면 무리 1개 추가된 것
        }
        //output
        sb.append("#"+t+" "+result+"\n");
    }
    System.out.print(sb);
}

느낀점

생략