[알고리즘 / JAVA] 바이러스 (백준)

바이러스

문제링크

핵심 아이디어

• 1번에서 시작하여 도달할 수 있는 컴퓨터의 개수를 확인
• DFS/BFS를 이용하며 탈출 조건을 설정

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int answer = 0;
        int n = sc.nextInt();
        int e = sc.nextInt();
		// Edge를 저장하기 위한 리스트
        List<Edge> list = new ArrayList<>();
        boolean[] visited = new boolean[n];

        for (int i = 0; i < e; i++) {
            list.add(new Edge(sc.nextInt(), sc.nextInt()));
        }
		// BFS를 위한 큐 생성
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        visited[0] = true;

        while (!queue.isEmpty()) {
            int now = queue.poll();

            for (Edge edge: list) {
            	// 연결되어있는 경우 진행
                if (edge.isConnected(now)) {
                    int next = edge.getConnectedVertex(now);
                    // 이미 체킹한 곳이면 큐에 삽입 X
                    if (visited[next - 1] == true) continue;

                    queue.add(next);
                    visited[next - 1] = true;
                    answer++;
                }
            }
        }

        System.out.println(answer);
    }
}

// Edge 클래스
class Edge {
    int start;
    int end;

	// 생성자
    Edge(int start, int end) {
        this.start = start;
        this.end = end;
    }

	// n번 vertex와 연관 판별 함수
    boolean isConnected (int n) {
        return n == start || n == end;
    }

	// n번 vertex와 짝을 이루는 번호 반환
    int getConnectedVertex (int n) {
        if (n == start) return end;
        return start;
    }
}

한줄평

Edge의 표현방식과 Queue 삽입 조건에 대한 고려가 필요한 문제