[BaekJoon] #2606 바이러스

문제이해

이 문제는 특정 노드와 연결되어 있는 노드의 개수를 세는 문제입니다.

BFS를 이용하여 시작정점에서 탐색을 시작해 인접 정점들을 모두 탐색하면 될 것 같습니다. 그냥 poll할때 마다 카운트를 찍어주면 됩니다! 짱쉬움

입력

컴퓨터의 수가 주어지고, 두번째는 연결되어 있는 컴퓨터 쌍의 수가 주어집니다.
이후, 연결되어있는 컴퓨터 번호 쌍이 주어집니다.

출력

1번 컴퓨터와 연결되어 있는 컴퓨터의 개수를 출력해주면 됩니다.

BFS는 시작 정점까지 포함해서 탐색하므로 자기 자신인 1을 제외하고 출력해주면 됩니다.

문제접근

입력값

• 입력을 위해 BufferedReader를 사용해주었습니다.
• adjList리스트와 visited [ ] 배열은 인덱스와 정점에 적힌 숫자를 일치시켜
  1-based인덱스로 만들어주기 위해 각각 n+1크기로 생성해주었습니다.
  

그래프 생성 (LinkedList)

• 각 정점에 대한 인접 정점들을 저장할 LinkedList 객체를 각각의 인덱스에 저장합니다.
• 무방향 그래프이므로, 간선이 양방향으로 연결되기 때문에 양쪽 정점에 모두 값을 추가해줘야 합니다.
• Collections.sort() 메서드를 이용해 각 정점에 연결된 인접 정점들을 정렬해줍니다.
  

BFS

• BFS는 시작 정점에서부터 너비 우선 탐색을 수행하며, 인접한 정점들을 차례대로 방문합니다.
• 큐(Queue)를 사용하여, 현재 정점의 인접 정점들을 탐색하며, 아직 방문하지 않은 정점들을 차례대로 큐에 넣어 방문합니다.
• 개수만 구하면 되므로, count를 이용해 탐색한 정점의 개수를 셌고, 1번 컴퓨터를 제외하여 1을 뺀 값으로 출력해주었습니다.
  

code

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

public class Main{
        public static void main(String[] args) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine()); // 정점의 수
            int m = Integer.parseInt(br.readLine()); // 간선의 수
            StringTokenizer st ;
            LinkedList<Integer>[] adjList = new LinkedList[n+1];
            boolean[] visited = new boolean[n+1];

            for(int i=0; i<=n; i++){
                adjList[i] = new LinkedList<Integer>();
            }
            for(int i=0; i<m; i++){
                st = new StringTokenizer(br.readLine());
                int v1 = Integer.parseInt(st.nextToken());
                int v2 = Integer.parseInt(st.nextToken());
                adjList[v1].add(v2);S
                adjList[v2].add(v1);
            }

            for(int i=1; i<=n; i++){
                Collections.sort(adjList[i]);
            }
            bfs(1,adjList,visited);

        }
            static void bfs(int v,LinkedList<Integer>[] adjList , boolean visited[]){
                int count = 0;
                Queue<Integer> q = new LinkedList<Integer>();
                visited[v] = true;
                q.add(v);
                while(!q.isEmpty()){
                    v = q.poll();
                    ++ count;
                    Iterator<Integer> iter = adjList[v].listIterator();
                    while(iter.hasNext()){
                        int w = iter.next();
                        if (!visited[w]){
                            q.add(w);
                            visited[w] = true;
                        }
                    }
                }
                System.out.println(count-1);
            }
    }