(#11724 Java) 연결 요소의 개수

 

문제 좀 잘 읽자...!! N이 1부터인데, 이번에도 습관처럼 계속 반복문의 범위를 for (int i = 0; i < N; i++) { } 이렇게 해서 계속 틀렸다...ㅎ 정신차렷~~~~!!

 

문제 해결

 

역시나 static 변수로 설정할 것들 먼저 선언해주자!

static int N,M;
static int[][] Graph;
static boolean[] Visited;
static int count;

 

 

dfs 함수이다. N 범위 주의!!!!!

public static void dfs(int node) {
    Visited[node] = true;

    for (int i = 1; i < N+1; i++) { //N이 1부터이므로 범위 설정 주의!!
        if(!Visited[i] && Graph[node][i] == 1)
            dfs(i);;
    }
}

 

 

main 함수이다.  전형적인 dfs 문제 알고리즘대로 따라가면 되는 간단한 문제였다.

좌표 그대로를 받아들이기 위해 배열 범위를 N+1로 해주는 것만 주의하면 어려움 없을 것이다.

public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        N = in.nextInt();
        M = in.nextInt();

        //좌표를 그대로 받아들이기 위해 N+1 크기로 선언.
        Graph = new int[N+1][N+1];
        Visited = new boolean[N+1];

        for (int i = 0; i < M; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            Graph[u][v] = Graph[v][u] =  1;
        }

        count = 0; //count 초기화 선언 위치 주의

        for (int i = 1; i < N+1; i++){ //N범위 주의..!
            if(!Visited[i]){
                dfs(i);
                count++;
            }
        }

        System.out.println(count);

    }

}

 

 

최종코드

 

package org.example.DfsBfs;

import java.util.Scanner;

public class NumberOfConnectingElements {

    static int N,M;
    static int[][] Graph;
    static boolean[] Visited;
    static int count;

    public static void dfs(int node) {
        Visited[node] = true;

        for (int i = 1; i < N+1; i++) { //N이 1부터이므로 범위 설정 주의!!
            if(!Visited[i] && Graph[node][i] == 1)
                dfs(i);;
        }
    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        N = in.nextInt();
        M = in.nextInt();

        //좌표를 그대로 받아들이기 위해 N+1 크기로 선언.
        Graph = new int[N+1][N+1];
        Visited = new boolean[N+1];

        for (int i = 0; i < M; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            Graph[u][v] = Graph[v][u] =  1;
        }

        count = 0; //count 초기화 선언 위치 주의

        for (int i = 1; i < N+1; i++){ //N범위 주의..!
            if(!Visited[i]){
                dfs(i);
                count++;
            }
        }

        System.out.println(count);

    }

}