[백준]11724_연결 요소의 개수_BFS Java 풀이(반례 포함)

사이트 링크

11724번: 연결 요소의 개수

11724번: 연결 요소의 개수

개념 및 풀이

그래프의 정점만큼 for문을 돌면서 BFS로 탐색하여 그 정점과 이어졌는지 확인한다.

visit[] : 이미 이어졌는지 확인했다면 1, 아니면 0

 

for문

• 아직 이어지지 않은 정점이라면 - 정점과 이어진 정점 확인하는 bfs() 함수 
  • 이을 수 있는 모든 정점 잇기
  • 이을수 있는 것 다 이었는데도 안이어진 정점은 같은 무리에 속하지 않는 것-> ans++

 

 

 

오류 해결(40%대에서 오류) - 양방향으로 연결하지 않았기 때문이었음

반례 :

5 4
1 2
3 2
3 4
4 5

-> 단방향이라면 2에서 연결될 것이 없기 때문에 같은 무리라고 판단하지 못해서 실제로 답은 1이지만 2가 나옴.

 

 

 

코드

package BFSDFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_11724 {
    static int N,M;
    static int map[][];
    static boolean visit[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N+1][N+1];
        visit = 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; // 양방향으로 해주지 않았더니 40%정도에서 틀림
        }

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            if(!visit[i]) {
                bfs(i);
                ans++;
            }
        }
        System.out.println(ans);
    }
    static void bfs(int i) {
        visit[i] = true;
        Queue<Integer> q = new LinkedList<>();
        q.offer(i);

        while(!q.isEmpty()) {
            int now = q.poll();

            for (int j = 1; j <= N; j++) {
                if(map[now][j]==1 && !visit[j]) {
                    q.offer(j);
                    visit[j] = true;
                }
            }
        }
    }
}