[백준 11724] 연결 요소의 개수 / DFS, JAVA

1. 첫번째 작성한 코드

import java.io.*;
import java.time.Year;
import java.util.*;

public class Main {
    static int n, m;
    static int cnt = 0;
    static ArrayList<ArrayList<Integer>> list;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        list = new ArrayList<ArrayList<Integer>>();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        for(int i=0; i<=n; i++) {
        	list.add(new ArrayList<Integer>());
        }
        for(int i=0; i<m; i++) {
        	st = new StringTokenizer(br.readLine());
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	list.get(a).add(b);
        	list.get(b).add(a);
        	list.get(a).sort((k,j)->k-j);
        	list.get(b).sort((k,j)->k-j);
        }
        visited = new boolean[n+1];
        int k = searchVisited();
        while(k<=n) {
        	dfs(k);
        	k = searchVisited();
        }
        System.out.println(cnt);
    }

    public static void dfs(int x) {
    	if(x<1 || x>n) return;
    	visited[x]=true;
    	for(int i=0; i<list.get(x).size(); i++) {
    		int y = list.get(x).get(i);
    		if(!visited[y]) dfs(y);
    	}
    }
    
    public static int searchVisited() {
    	int i=0;
    	for(i=1; i<visited.length; i++) {
    		if(!visited[i]) break;
    	}
    	if(i>0 && i<=n) cnt++;
    	return i;
    }
}

dfs메서드와 카운트를 해줄 수 있는 searchedVisited 메서드를 만들어서 문제를 풀었다. 그러나 코드의 길이가 너무 길고, 메모리는 시간은 5512ms 소요되어 너무 비효율적이기 때문에 코드 개선이 필요하다.

=> 각 요소의 방문 순서가 중요하지 않기에, sort 코드를 삭제해주니 시간이 760ms로 감소했다.

=> 굳이 searchedVisited 메서드를 만들지 않고, 첫번째 요소부터 for문으로 탐색하면 코드가 더 간결해질 수 있음

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

public class Main {
  static int n, m;
  static ArrayList<ArrayList<Integer>> list;
  static boolean[] visited;

  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      list = new ArrayList<ArrayList<Integer>>();
      n = Integer.parseInt(st.nextToken());
      m = Integer.parseInt(st.nextToken());
      for(int i=0; i<=n; i++) {
      	list.add(new ArrayList<Integer>());
      }
      for(int i=0; i<m; i++) {
      	st = new StringTokenizer(br.readLine());
      	int a = Integer.parseInt(st.nextToken());
      	int b = Integer.parseInt(st.nextToken());
      	list.get(a).add(b);
      	list.get(b).add(a);
      }
      visited = new boolean[n+1];
      int cnt = 0;
      for(int i=1; i<=n; i++) {
      	if(!visited[i]) {
      		dfs(i);
      		cnt++;
      	}
      }
      System.out.println(cnt);
  }

  public static void dfs(int x) {
  	visited[x]=true;
  	for(int i:list.get(x)) {
  		if(!visited[i]) dfs(i);
  	}
  }
}

아래에서부터 첫 코드, sort를 제거한 코드, searchedVisited를 제거한 코드의 소요시간