[백준 11724 - 연결 요소의 개수] DFS를 활용한 문제 풀기

 

위 문제는 DFS풀이의 가장  기본적인 문제이다.

 

문제를 풀기에 앞서 풀이 순서를 짚어보자.

1. 최대 정점의 개수와 문제풀이 시간을 대조해본다.
   -  문제 풀이 시간은 3초이다. 최대 노드의 개수는 1000개로 n^2의 복잡도로 문제를 풀어도 충분히 시간이 남는다.

2. 해당 그래프를 직접 그려본다.

    - 첫 예시의 그래프를 만들어보자면 다음과 같다. (혼을 담아 정성스럽게 그려보았다)

3. 이처럼 두개의 그래프가 그려지는것을 확인할 수 있다. 이를 코드로 작성하기 위한 슈도코드를 작성해본다.

n(노드 개수) , m(엣지 개수)

A(그래프 데이터 저장 인접 리스트)

visited(방문 기록 저장 배열)

for(n만큼 반복
{A 인접 리스트의 각 ArrayList초기화}

for(m의 개수만큼 반복하기)
{ A인접 리스트에 그래프 데이터 저장하기 }

for(n의 개수만큼 반복하기)
{ if(방문하지 않은 노드가 있으면){ 연결 요소 개수 ++ DFS 실행하기 }

//DFS구현하기
{
DFS{ if(현재 노드 == 방문노드) return;
visited 배열에 현재 노드 방문 기록하기
현재 노드의 연결 노드 중 방문하지 않는 노드로 DFS 실행하기(재귀 함수 형태)
}

 

4.이를 토대로 재귀함수를 사용한 스택형식의 DFS를 구현한다.

public class test {
    //방문 배열
    static boolean[] visited;
    //인접 리스트
    static ArrayList<Integer>[] A;
    
    public static void main(String[] args) throws IOException {

        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());
       
        visited = new boolean[n+1];
        A = new ArrayList[n + 1];
        for (int i = 1; i < n + 1; i++) {
            //인접리스트배열 초기화
            A[i] = new ArrayList<Integer>();
        }
        //인접 리스트에 그래프 데이터 저장
        for (int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            A[s].add(e);
            A[e].add(s);
        }
        //개수를 판단할 count변수
        int count =0;

        //방문배열에 등록되지 않은 노드를 재귀함수를 통해 찾아냄
        for (int i = 1; i <n+1; i++) {
            if(!visited[i]) {
                count++;
                DFS(i);
            }
        }
        System.out.println(count);
      
    }

    private static void DFS(int v) {
        if(visited[v]){
            return;
        }
        visited[v] = true;

        for (int i : A[v]) {
            if (!visited[i]) {
                
                DFS(i);
            }
        }
    }
}