자 이제 시작이야

요즘 카카오 부트캠프 수업을 들으면서 깊이있는 탐구라는것이 나에게 얼마나 흥미와 관심을 가져다 주는지 모르겠다. 하지만 마음 한 편에는 우주를 공부하는 것에 막연한 기대감을 놓지 못하고 있다. 허성범의 강의를 보았고 좋아하는 것을 남들의 시선을 신경쓰지말고 최선을 다하며 하다보면 후회는 남지 않을 것이다라는 말을 되새기며 지금 하고 있는 일에 최선을 다해보려고 한다. 만약 이것이 정녕 내가 싫어하는 일이더라도 후회는 남기고 싶지 않기 때문이다. 🙈
(들어가는 이야기, 제리라는 풀스택 팀원 덕분에 해당 부분에 대한 즐거움(?)을 알게되었다.)

BFS는 Breadth의 뜻이 가장 두드러지는 노드 탐색 방법이다. 노드와 노드끼리 연결되어 있다면 한 방향으로 계속 탐색하는 것이 아닌, 이어진 주변 노드에 계속 발을 걸치는 것이다. 하지만 실제 구현은 설계와는 다른 아이러니한 점이 발생한다.

간단히 생각해보면 노드를 방문해야 방문처리를 하지만, 구현에서는 해당 노드를 방문할 예정이라고 장바구니 담듯이 담아놓는 큐에 담을 때마다 방문처리를 하는 것이다. 왜냐하면 또다른 연결된 다른 노드에 의해 한번더 중복으로 특정 노드가 한번 더 담길 수 있기 때문이다.

결론적으로 너비 우선 탐색으로 하는 BFS는 방문시에 방문체크를 한다고 하지만 정확히 말하면, 방문하기로 한 노드를 선별하는 타이밍에 방문 체크를 해줘야한다는 것이다. 바로 문제풀이로 넘어가보자

🔍 Problem

백준 11724

---

📃 Input&Output

---

🌁 문제 배경

가. 문제 설명
BFS를 사용하여 총 경로의 개수를 구하는 것

나. 접근 방법
BFS를 여러번 돌리며, BFS가 실행된 개수 = 경로의 수 라는 메커니즘으로 해결하였다.

다. 문제 유형
BFS

---

📒 수도 코드

가
Bfs에 While문 씌우기

---

💻 Code

import java.util.*;
import java.io.*;

public class P23 {
    static int cnt=0;

    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;

        int N,M;

        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        int[][] graph = new int[N+1][N+1];
        boolean[] vst = new boolean[N+1];

        for (int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        BFS(vst, graph);

        bw.write(cnt+"");
        bw.flush();

        bw.close();
    }

    static void BFS(boolean[] vst, int[][] graph){

        Queue<Integer> que = new LinkedList<>();

        for (int i=1; i<vst.length; i++){
            if(!vst[i]){
                que.add(i);
                while(!que.isEmpty()){
                    int n = que.poll();
                    for (int j=1; j<vst.length; j++){
                        if (graph[n][j] == 1 && !vst[j]  ){
                            que.add(j);
                            vst[j]=true;
                        }
                    }
                }
                cnt++;
            }
        }
    }
}

🤔 느낀점

재미를 느끼고 싶다