[백준] 재풀이 11724 : 연결 요소의 개수 - JAVA

DFS를 처음 다루어보고, 너무 어려워서 이 문제를 다시 풀었다.
그런데,, 또 틀렸다!

Troubleshooting 1

public class connectionCount {
static ArrayList<Integer>[] arrList;
static boolean[] visited;

	static void DFS(int candidate) {
		if(visited[candidate]) {
			return;
		}
		visited[candidate] = true;
		for(int i : arrList[candidate]) {
			if(!visited[i]) DFS(i);
		}
	}

	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int connectionCnt = 0;
		int n = Integer.parseInt(st.nextToken());
		int m  = Integer.parseInt(st.nextToken());
		arrList = new ArrayList[n];
		visited = new boolean[n];
	
		for(int index = 0 ;index<m ; index++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			arrList[u].add(v); //java.lang.NullPointerException 발생
			arrList[v].add(u);
		}
		for(int j =0 ; j<n; j++) {
			if(!visited[j]) {
				connectionCnt++;
				DFS(j);
			}
		}
		System.out.println(connectionCnt);
	}
}

문제

실행하며 예제 입력 1의 두번째 줄 '1 2'를 입력할 때,java.lang.NullPointerException이 발생했다.

이 에러는 null값을 가지는 객체 참조를 사용하려할 때 발생한다.

원인

intArr은 ArrayList타입을 원소로 가진, 2차원 배열이다.
내가 짠 코드에서는 intArr의 큰 틀인 배열만 초기화했고, 그 속의 원소인 ArrayList는 초기화하지않은채로 u,v를 대입했다.

해결

u,v를 받아 intArr에 대입하기 전에 intArr의 원소로 있는 ArrayList도 초기화해주었다.

Troubleshooting 2

public class connectionCount {
static ArrayList<Integer>[] arrList;
static boolean[] visited;

	static void DFS(int candidate) {
		if(visited[candidate]) {
			return;
		}
		visited[candidate] = true;
		for(int i : arrList[candidate]) {
			if(!visited[i]) DFS(i);
		}
	}

	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int connectionCnt = 0;
		int n = Integer.parseInt(st.nextToken());
		int m  = Integer.parseInt(st.nextToken());
		arrList = new ArrayList[n];
		visited = new boolean[n];
		for(int k=0;k<n; k++) {
			arrList[k] = new ArrayList<Integer>();
		}
	
		for(int index = 0 ;index<m ; index++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			arrList[u].add(v);
			arrList[v].add(u);
		}
		for(int j =0 ; j<n; j++) {
			if(!visited[j]) {
				connectionCnt++;
				DFS(j);
			}
		}
		System.out.println(connectionCnt);
	}
}

문제

java.lang.ArrayIndexOutOfBoundsException: Index 6 out of bounds for length 6가 발생했다.

원인

문제설명을 보면, u,v가 1이상이다. 즉, 프로그래밍에서 사용되는 배열 인덱스의 개념과 조금 다르다.

해결

프로그래밍에서는 인덱스 0부터 시작이므로, 실제 배열의 인덱스 0에 해당하는 값을 비워두고, 인덱스1부터 초기화 및 사용한다.

제출코드

public class connectionCount {
static ArrayList<Integer>[] arrList;
static boolean[] visited;

	static void DFS(int candidate) {
		if(visited[candidate]) {
			return;
		}
		visited[candidate] = true;
		for(int i : arrList[candidate]) {
			if(!visited[i]) DFS(i);
		}
	}

	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int connectionCnt = 0;
		int n = Integer.parseInt(st.nextToken());
		int m  = Integer.parseInt(st.nextToken());
		arrList = new ArrayList[n+1];
		visited = new boolean[n+1];
		for(int k=1;k<n+1; k++) {
			arrList[k] = new ArrayList<Integer>();
		}
	
		for(int index = 0 ;index<m ; index++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			arrList[u].add(v);
			arrList[v].add(u);
		}
		for(int j =1; j<n+1; j++) {
			if(!visited[j]) {
				connectionCnt++;
				DFS(j);
			}
		}
		System.out.println(connectionCnt);
	}
}

내가 부족한 부분!

DFS를 이용한 로직을 짤 때에는 배열과 재귀함수로 구현하는데, 이를 구현하기위한 전체 로직 구성에 약하다.

큰틀은 이렇다.

요점

• 메소드는 main(), DFS() 선언
• 가장 밖에 main,DFS 둘 다에서 사용하는 변수 선언
• DFS는 방문했으면 끝내고(이 부분 꼭 필요! 재귀함수로인해 타고타고 여러번 호출되므로, 방문했을 시 해당 루프는 끝내도록 함), 그렇지않았을 때 해당 방문배열 true대입.(DFS를 호출하는것이 방문하는 행위임)
• 2차원 배열이므로 겉 배열 내부에있는 ArrayList 원소를 for문으로돌아 방문체크함. 방문하지 않았으면 DFS 호출(재귀)