[알고리즘] 바이러스

package org.example.바이러스;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.InvalidObjectException;
import java.text.MessageFormat;
import java.util.*;

/* *
 *
 *
 *
 *
 *
 *
 *
 *  */
public class Main {
    public static void main(String[] args) {
        // 해당 문제는 출력이 1회라 별도 PrintWriter를 사용하지 않고 System.out.println()을 사용하였다.
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) {
            int computerCount = Integer.parseInt(br.readLine());
            
            // 컴퓨터의 수는 100 이하인 양의 정수입니다.
            if (!(1 <= computerCount && computerCount <= 100)) {
                String errorMessage = MessageFormat.format("computerCount must be between 1 and 100. (actual: {0})", computerCount);
                throw new InvalidObjectException(errorMessage);
            }
            int[][] graph = new int[computerCount][computerCount];
            boolean[] visited = new boolean[computerCount];
            int networkCount = Integer.parseInt(br.readLine());
            
            for (int i = 0; i < networkCount; i++) {
                String input = br.readLine();
                StringTokenizer st = new StringTokenizer(input, " ");
                int computer1 = Integer.parseInt(st.nextToken());
                int computer2 = Integer.parseInt(st.nextToken());
                graph[computer1 - 1][computer2 - 1] = 1;
                graph[computer2 - 1][computer1 - 1] = 1;
            }
            int answer = bfs(graph, visited, 0);
            System.out.println(answer);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    
    private static int bfs(int[][] graph, boolean[] visited, int start) {
        Queue<Integer> queue = new LinkedList<>();
        int count = 0;
        visited[start] = true;
        queue.offer(start);
        while (!queue.isEmpty()) {
            int polled = queue.poll();
            for (int i = 0; i < graph.length; i++) {
                if (graph[polled][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    queue.offer(i);
                    count++;
                }
            }
        }
        return count;
    }
    
}
// 처음에 클래스 구조로 짜려고했지만, 해당 BFS DFS 문제를 객체지향적으로 구조화하는 방법을
// 모르겠습니다..
// 클래스 구조를 유지하면서 순회를 어떻게 돌 수 있을까요 ㅠㅠ..

1. 초기 구상
   • 처음엔 클래스 구조로 구상하였다.
   • Computer 클래스를 만들어서 2차원 객체배열을 만들 생각을 하였지만, 값이 비어있는 경우 null 값으로 들어가서 불안정한 구조라고 생각했다.

2. 이후 구상
   • 단순하게 graph 2차원 배열을 이용하여
   • 행 - 열 기준으로

     

     • 2컴퓨터와 3컴퓨터가 연결된 경우 2차원 배열에서의 각 행 - 열 구조로 1표시를 해주었다.

3. 나머지 로직은 BFS를 알고있으면 쉬운 문제라 그냥 생략

Uploaded by N2T