[백준 BOJ/Silver II] 11724번 : 연결 요소의 개수

 

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

11724번: 연결 요소의 개수

 

- 방향이 없는 그래프는 양방향으로 값을 넣어줘야한다

예를 들어 (1, 5) 연결과 (5, 1) 연결이 같으므로 처음 입력받을때 양쪽 모두 1이 들어가도록 해주어야한다

- 해당 정점을 확인했는지 표시해주는 boolean 배열도 필요하다

- 1번 정점을 시작으로 그거와 연결된 정점들을 확인하며 아직 방문하지 않은 정점이라면 큐에 넣고빼고를 반복하며 연결되어있는 것을 모두 돌고와서 count++ 해준다

- 방문하지 않은 정점이 남아있다면 그 정점을 시작으로 확인하는 과정을 반복해준다

- 모든 정점을 방문했다면 count를 출력해준다

 

 

일반 dfs, bfs 문제보다 그래프로 나오는 문제가 더 낯설고 헷갈린다,,

많은 연습 필요!!!

 

최종 코드

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int N;
    static int M;
    static int[][] graph;
    static boolean[] visited;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        graph = new int[N+1][N+1];
        visited = new boolean[N+1];

        for(int i = 0; i < M; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph[x][y] = 1;
            graph[y][x] = 1;
        }

        int count = 0;
        for(int i = 1; i < N+1; i++) {
            if(!visited[i]) {
                bfs(i);
                count++;
            }
        }
        System.out.println(count);
    }

    static void bfs(int x) {
        Deque<Integer> dq = new ArrayDeque<>();
        dq.addLast(x);
        visited[x] = true;

        while (!dq.isEmpty()) {
            int point = dq.pollFirst();

            for(int i = 1; i < N+1; i++) {
                if(graph[point][i] == 1 && !visited[i]) {
                    dq.addLast(i);
                    visited[i] = true;
                }
            }
        }

    }
}

 

 

아싸 실버2 됐다!! 골드까지 화이팅👊👊👊