2606번 - 바이러스

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

public class Main {
	
	static class Node {
		int v;
		Node next;
		
		Node(int v, Node next) {
			this.v = v;
			this.next = next;
		}
	}
	
	static int cnt;
	static boolean[] visited;
	
	static void dfs(int v, Node[] adjList) {
		visited[v] = true;
		cnt++;
		for(Node node=adjList[v];node != null;node = node.next) {
			if(!visited[node.v]) {
				dfs(node.v, adjList);
			}
		}
	}
	
	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());
		Node[] adjList = new Node[N+1];
		int start, end;
		StringTokenizer st;
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());
			adjList[start] = new Node(end, adjList[start]);
			adjList[end] = new Node(start, adjList[end]);
		}
		cnt = -1;
		visited = new boolean[N+1];
		dfs(1, adjList);
		System.out.println(cnt);
		br.close();
	}
}

연결 리스트를 구현하고 탐색할 수 있는지 묻는 문제입니다.

연결 리스트를 구현하는 방법에는 대표적으로 인접 행렬과 인접 리스트가 있는데 여기서는 인접 리스트로 구현했습니다.

인접 리스트의 경우 노드의 개수 크기만큼의 배열을 선언하고 연결 상태를 받아서 노드 번호를 인덱스에 매칭하여 해당 인덱스에 노드에 연결된 노드들이 계속 이어지도록 구현합니다.(배열로 저장하는 방법이 있고 포인터로 저장하는 방법이 있는데 여기서는 포인터를 사용했습니다.)

 

인접 리스트의 경우 방향성을 띠기 때문에 이 경우에는 입력이 들어오면 양쪽 방향 모두 등록을 해야 정상적으로 탐색할 수 있습니다.

 

입력이 완료되면 boolean 배열로 방문한 노드를 표시하면서 1번 노드에 연결된 노드의 개수를 세면 해결됩니다.