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

문제링크

11724번: 연결 요소의 개수

 

 

접근한 방법

• dfs

 

---

풀이방법

 

2021.05.04 - [알고리즘/DFS BFS] - DFS에 있는 DFS 예제 중 인접행렬을 참고하였다.

 

• dfs 메소드를 선언하여 파라미터를 노드 번호로 받는다.
• 현재 노드를 방문 처리하고,
  그 노드와 연결되어 있으며 방문하지 않은 노드를 방문한다 (dfs 메소드를 호출한다).
• 해당 노드의 dfs 메소드 호출이 끝나면 결과를 더해줌으로 써 연결 노드의 개수를 구한다.

 

---

소스코드 작성 방법

• 인접행렬을 이용한다 (인접 행렬 관련은 글 참조)
• 노드가 연결된 정보, 노드 방문 여부, 연결된 노드 횟수를 전역 필드로 선언한다.
• 방향이 없으므로 입력을 받을 때 map[u][v] 도, map[v][u]도 1로 선언해준다.
• dfs 메소드의 인자를 노드 번호(u)로 받는다.
  • vistied[u] = true로 하여 방문 처리
  • map의 u번째 행의 모든 노드를 검사하여
    map[u][i] = 1이고 (연결되어있고) visited[i] = false로 아직 방문하지 않은 노드라면
    dfs 메소드를 재귀적으로 호출하여 방문수행
• solution 메소드에서 1번 노드부터 마지막 번호 노드까지 탐색을 수행한다.
  * 방문하지 않은 노드만 방문 수행 !
  dfs 메소드 호출이 끝나면 result ++를 하여 연결된 노드 수를 더해준다.

---

 

실수한 점 & 부족한 점

• solution() 메소드에서 방문하지 않은 것만 dfs() 호출하도록 처리하지 않았던 점
• solution() 메소드에서 if(!visited[i]) 로 방문여부 검사하지 않았을 때 예시 ) 더보기 클릭

---

---

 

소스코드

package baekjoon.dfs_bfs;
import java.io.*;
import java.util.StringTokenizer;

public class Q_11724_TheNumberOfConnecting_20210521 {
    public static int[][] map ; // 노드가 연결된 정보
    public static boolean[] visited; // 노드 방문 여부
    public static int result = 0; // 연결된 노드 횟수

    public static void solution(){
        for(int i=1 ; i<map.length ; i++){
            // 방문하지 않은 노드만 방문
            if(!visited[i]){
                dfs(i);
                result ++;
            }
        }
    }
    public static void dfs(int u){
        // 방문 처리
        visited[u] = true;

        for(int i=1 ; i<map.length ; i++){
            // 노드와 연결되어 있으며 방문하지 않은 노드를 방문
            if(map[u][i] == 1 && !visited[i])
                dfs(i);
        }
    }

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        map = new int[n+1][n+1];
        visited = new boolean[n+1];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            map[u][v] = 1;
            map[v][u] = 1;
        }

        solution();
        bw.write(result+"");

        br.close();
        bw.close();
    }
}