[백준 / DFS] (틀림)#11724 연결 요소의 개수 (java)

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

 

 

[문제접근]

그래프를 생성 후 dfs를 돈다.

그래프 생성은 인접리스트로 한다.

내가 계속 무언가 헤매고 있었던 이유는 java에서의 인접리스트 구현이 익숙하지 않기 때문이라고 결론을 내렸다. 

(C에서 구현하는거에만 익숙해져서)

그래서 java에서 인접리스트 구현은 다른 분들의 코드를 참고했다.

 

[java코드]

import java.io.*;
import java.util.*;

public class Main {

	static ArrayList<Integer>[] adjList;
	static boolean visited[];
	
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		adjList = new ArrayList[N+1];
		visited = new boolean[N+1];
		
		int vertex1, vertex2, answer = 0;
		
		for(int i=1; i< N+1; i++) {
			adjList[i] = new ArrayList<Integer>();
			//인접리스트 구현  
		}
		
		for(int i = 0; i < M; i++) {
			vertex1 = Integer.parseInt(st.nextToken());
			vertex2 = Integer.parseInt(st.nextToken());
			adjList[vertex1].add(vertex2);
			adjList[vertex2].add(vertex1);
			// 무방향 그래프이므로   
		}
		
		for(int i = 1; i < N+1; i++) {
			if(!visited[i]) {
				dfs(i);
				answer++;
			}
		}
		System.out.println(answer);
	}
	
	static void dfs(int v) {
		if(visited[v]) {
			return;
		}
		visited[v] = true;
		for(int i :adjList[v]) {
			if(!visited[i]) {
				dfs(i);
			}
		}
	}

}

런타임에러

 

 

 

[참고]

이 분 해설이 정리가 잘 되어있다. 

https://hees-dev.tistory.com/m/46?category=824514

[BOJ] 백준 11724 연결 요소의 개수-java

 

[문제 링크]

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수