문제 링크: https://www.acmicpc.net/problem/2606

문제

해설

매우 전형적이고 기본적인 BFS, DFS를 통한 그래프 탐색 문제이다. BFS, DFS 이론을 차근차근 적용해나가면 누구나 풀 수 있는 쉬운 문제이다. BFS와 DFS에 대한 개념이 잘 설명되어 있는 포스팅은 워낙 많다보니 해당 포스팅에서는 BFS와 DFS의 개념은 따로 설명하지 않겠다.

BFS, DFS 두 가지 모든 방식으로 풀어보겠다.

BFS

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N, M;
    static List<Integer>[] graph;
    static boolean[] visited;
    static int count;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine()); // 컴퓨터(노드)의 수
        M = Integer.parseInt(br.readLine()); // 간선의 수

        // 그래프 초기화
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>(); // 1 ~ N번 인덱스에 각각 빈 리스트 할당
        }

        while (M-- > 0) {
            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);
        }

        // 방문 체크 배열 초기화
        visited = new boolean[N + 1];
        
        // 1번 컴퓨터가 감염시킨 컴퓨터 수(1번 노드와 연결된 노드 수) 초기화
        count = 0;

        // bfs 실행(bfs로 그래프 탐색해서 1번 노드와 몇 개의 노드가 연결되어 있는지 확인)
        sb.append(bfs(1));
        System.out.println(sb);

    }

    private static int bfs(int x) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(x); // 큐에 1번 컴퓨터(노드) 추가
        visited[x] = true; // 1번 노드 방문 처리
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int next : graph[cur]) { // 현재 노드와 인접한 노드들 순차적으로 탐색
                if (!visited[next]) { // 해당 노드를 아직 방문 전이라면 로직 처리
                    count++;
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
        return count;

    }
}

Python

import sys
from collections import deque
input = sys.stdin.readline


N = int(input())  # 노드 수
M = int(input())  # 간선 수

# 노드 연결 정보 담은 그래프 초기화
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (N + 1)  # 노드 방문 여부 확인 리스트
count = 0  # 1번 컴퓨터가 감염시키는 연결된 컴퓨터의 수


def bfs(x):
    """bfs로 그래프 탐색해서 1번 노드와 몇 개의 노드가 연결되어 있는지 확인"""
    global count
    queue = deque([x])
    visited[x] = True
    while queue:
        cur = queue.popleft()
        for next in graph[cur]:
            if not visited[next]:
                count += 1
                visited[next] = True
                queue.append(next)

    return count


print(bfs(1))  # 1번 노드에서 시작해 bfs 실행

DFS

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N, M;
    static List<Integer>[] graph;
    static boolean[] visited;
    static int count;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine()); // 컴퓨터(노드)의 수
        M = Integer.parseInt(br.readLine()); // 간선의 수

        // 그래프 초기화
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        while (M-- > 0) {
            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);
        }

        // 방문 체크 배열 초기화
        visited = new boolean[N + 1];

        // 1번 컴퓨터가 감염시킨 컴퓨터 수 초기화
        count = 0;

        // dfs 실행(dfs로 그래프 탐색해서 1번 노드와 몇 개의 노드가 연결되어 있는지 확인)
        sb.append(dfs(1));
        System.out.println(sb);

    }

    private static int dfs(int x) {
        visited[x] = true; // 중복 안 되게 이미 카운트한 노드(컴퓨터) 방문 처리
        for (int next : graph[x]) { // 현재 노드와 인접 노드들 탐색
            if (!visited[next]) { // 아직 방문 X 노드라면
                count++; // 카운트
                dfs(next); // 재귀 호출
            }

        }
        return count;
    }
}

Python

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())  # 노드 수
M = int(input())  # 간선 수

# 노드 연결 정보 담은 그래프 초기화
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (N + 1)  # 노드 방문 여부 확인 리스트
count = 0  # 1번 컴퓨터가 감염시키는 연결된 컴퓨터의 수


def dfs(x):
    """dfs로 그래프 탐색해서 1번 노드와 몇 개의 노드가 연결되어 있는지 확인"""
    global count  # global로 count 전역 변수로 선언해 함수 내에서도 수정 가능
    visited[x] = True  # base case(해당 노드의 visited가 True일 시 재귀 탈출)
    for next in graph[x]:
        if not visited[next]:
            count += 1
            dfs(next)

    return count


print(dfs(1))