📍 문제

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

그래프 (Graph)

여러 개의 점(노드)과 이 점들을 연결하는 선(간선)으로 이루어진 구조.

• 노드: 컴퓨터. 컴퓨터1, 2, 3 .. 처럼 번호가 매겨진 점
• 간선: 두 컴퓨터가 네트워크로 연결되어있다면 그것이 간선.

DFS | BFS

그래프에 있는 모든 노드들을 탐색하기 위한 두 가지 방법.

DFS(Depth-First Search): 깊이 우선 탐색

한 방향으로 깊이 내려가면서 탐색하는 방법.

한 노드를 방문하면 그 노드에 연결된 다른 노드로 쭉 가다가,
더 이상 방문할 곳이 없으면 되돌아온다.

• 방문한 노드는 기록하여 다시 방문하지 않게 한다.
• 예를 들어 컴퓨터 1 → 2 → 3 처럼 한 쪽으로 가다가 더 이상 연결된 노드가 없으면 뒤로 돌아가서 다른 경로를 탐색한다.
  • ex. 2번으로 돌아가서 연결된 다른 컴퓨터인 5번 , 6번 으로 이동

BFS(Breadth-First Search): 너비 우선 탐색

가까운 노드부터 탐색하는 방법.

현재 노드에서 연결된 모든 노드를 먼저 탐색한 후,
그 다음 노드에 연결된 모든 노드를 탐색한다.

• ex.
  • 1번 → 2번, 5번 (1번과 연결된 모든 노드 먼저 탐색)
  • 2번 → 3번 (2번과 연결된 노드 탐색)
  • 5번 → 6번 (5번과 연결된 노드 탐색)

💡 두 방법 모두 그래프의 모든 노드를 탐색할 수 있다.
DFS 는 한 쪽 방향으로 깊게 파고들어 탐색해 스택 구조 / 재귀를 활용하고,
BFS 는 가까운 노드부터 시작, 탐색하여 큐 구조를 사용한다.

💻 답안 코드

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

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

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        ArrayList<Integer>[] graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        boolean[] visited = new boolean[N + 1];

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

            graph[a].add(b);
            graph[b].add(a);
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        visited[1] = true;
        int cnt = 0;
        while(!queue.isEmpty()){
            int node = queue.poll();
            for (int i : graph[node]) {
                if(!visited[i]){
                    queue.add(i);
                    visited[i] = true;
                    cnt++;
                }
            }
        }
        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
        br.close();
    }
}

💡

1번 컴퓨터에 대한 결과만 출력하기 때문에 따로 bfs 함수를 만들지 않고,
1의 경우의 카운트 값만 구해주었다.
dfs 로도 풀 수 있는 문제라 다음에는 dfs 로도 도전해보아야겠다 !