[Java] 백준 11724번 : 연결 요소의 개수 <Silver 2>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

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

11724번: 연결 요소의 개수

Code

---

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

public class  Main{

    void run() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] input = bf.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        boolean[][] graph = new boolean[N][N];
        boolean[] visited = new boolean[N];

        int count = 0;

        for(int i = 0; i < M; i++){
            input = bf.readLine().split(" ");
            graph[Integer.parseInt(input[0])-1][Integer.parseInt(input[1])-1] = true;
            graph[Integer.parseInt(input[1])-1][Integer.parseInt(input[0])-1] = true;
        }

        for(int i = 0; i < N; i++){
            if(visited[i] == false){
                BFS(graph, visited, i+1);
                count++;
            }
        }

        System.out.println(count);

    }

    void BFS(boolean[][] graph, boolean[] visited, int Start){
        visited[Start - 1] = true;
        Queue<Integer> queue = new LinkedList<>();
        int num = Start;

        queue.offer(Start);

        while(!queue.isEmpty()){
            num = queue.poll();

            for(int i = 0; i < visited.length; i++){
                if(visited[i] == false && graph[num-1][i] == true){
                    visited[i] = true;
                    queue.offer(i+1);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException{
        Main my = new Main();
        my.run();
    }
}

---

Code 필수 요소

1. BFS

2. 연결 요소의 개수 확인 방법

 

// BFS

큐를 사용하는 방식을 했다.

조건에 일치하는 값을 발견하면 큐에 넣고, 스택에서 값을 하나씩 꺼내며 출력 및 탐색을 하는 방식이다.

큐가 비었다면 더이상 탐색할 값이 없는 것이기때문에 반복을 종료한다.

 

// 연결 요소의 개수 확인 방법

생각보다 정말 간단하다. BFS가 작동되기 시작한다면 새로운 묶음이 존재한다고 판단하면 된다.

단, 여기서 조건을 하나 걸어줘야 한다. 모든 요소를 하나씩 확인하며 해당 요소가 이미 방문한 값인지를 확인해야한다.

확인한 결과 방문했다면 이미 어딘가에 연결되어있는 요소이기 때문에 추가로 탐색하지 않아도 된다. 그렇기 때문에 방문한 적 없는 요소를 발견하면 BFS를 작동시키고 count를 늘려주어 개수를 확인한다.

 

// 전체적 설명

그래프 탐색 알고리즘인 BFS를 잘 알고있냐를 묻는 문제.

 

BFS구현을 위한 가장 기본적인 visited 배열과 graph배열을 선언해주고 활용한다.

 

여기서 visited배열이란 탐색 과정에서 해당 요소를 탐색했는지 알려주는 배열이다. 이게 없다면 내가 탐색을 했는지 안했는지 몰라서 계속해서 탐색을 하게 된다. 내가 방문한 숫자의 인덱스를 true로 만들어줘서 내가 해당 번호를 방문햇다~를 기록한다.

 

graph배열이란 어느 숫자와 어느 숫자가 연결되어있는지를 나타내는거다. 예를들어 1과 2가 연결되어있다면 graph[0][1], graph[1][0]을 true로 만들어준다. 이렇게 될 경우 1에서 시작할때 2는 true이므로 연결되어있다는 것을 알 수 있다 반대도 마찬가지다. 연결되어있기때문에 해당 숫자로 탐색을 진행할 수 있다.

 

 

DFS와 BFS란?

https://naemamdaelo.tistory.com/37

알고리즘 - 깊이우선탐색(DFS), 너비우선탐색(BFS)

 

BFS를 활용할 수 있을줄 알았는데 거즌 그대로네. 생각보다 허무했다.

 

-꿑-