[do it 알고리즘] 백준 11724 (DFS)

문제 설명

 

풀기 전 생각

• DFS는 예전부터 어려워하던 코드라 슈도코드도 작성해보지 못하고 아이디어만 생각
• 방문 여부를 알 수 있는 visited [] 배열 생성
• 배열 또는 ArrayList로 인접 리스트 생성하여 저장
• 1부터 시작이므로 배열이나 ArrayList 크기를 N+1 
• 무방향 그래프 이므로 (시작선, 끝선) 서로 등록해 주기
• 방문했던 곳은 넘어가고 아니면 visited [i] = true로 바꾸고 DFS 계속 실행
• 총 진행된 DFS 횟수 = 연결 요소 개수 

코드 with 재귀함수

import java.util.*;
import java.io.*;
public class Baek11724 {
    public static ArrayList<Integer>[] arr; // 연결리스트로 만듬
    public static boolean visited[]; // 방문 여부 배열
    public static void main(String[] args) throws Exception {
        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];
        arr = new ArrayList[n+1]; // 연결리스트 객체 생성

        for(int i = 1; i < n+1; i++){
            arr[i] = new ArrayList<Integer>(); // 객체 하나하나에 연결 리스트 생성
        }

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            // 무방향 그래프 특성
            arr[start].add(end); 
            arr[end].add(start);
        }

        int count = 0;
        for(int i = 1; i < n+1;i++){
            if(!visited[i]){ // 방문 안했으면
                count++; // 처음 DFS 시작할때 +1
                DFS(i); // DFS 시작
            }
        }
        System.out.println(count);
    }
    public static void DFS(int v){
        if(visited[v]) return; // 이미 방문했으면 pass
        visited[v] = true; // 방문 안했으면 방문 표시
        for(int i : arr[v]){ // 리스트 요소들 돌면서
            if(!visited[i]){ // 방문 안했으면
                DFS(i); // DFS 진행
            }
        }
    }
}

새로 알게 된 점

1. 연결리스트와 방문 배열 선언은 전역 변수로 해주는 것이 편하다.
2. 리스트 하나하나에 for문을 돌면서 연결 리스트 생성해줘야 한다.
3. DFS는 stack과 재귀함수 두 개로 구현할 수 있다.
4. 위의 코드를 가지고 stack과 인접 배열로 작성해봤다.

코드 with stack

import java.util.*;
import java.io.*;
public class Main2 {
    public static ArrayList<Integer>[] arr; // 연결리스트로 만듬
    public static boolean visited[]; // 방문 여부 배열
    public static void main(String[] args) throws Exception {
        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];
        arr = new ArrayList[n+1]; // 연결리스트 객체 생성

        for(int i = 1; i < n+1; i++){
            arr[i] = new ArrayList<Integer>(); // 객체 하나하나에 연결 리스트 생성
        }

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            // 무방향 그래프 특성
            arr[start].add(end);
            arr[end].add(start);
        }

        int count = 0;
        for(int i = 1; i < n+1;i++){
            if(!visited[i]){ // 방문 안했으면
                count++; // 처음 DFS 시작할때 +1
                DFS(i); // DFS 시작
            }
        }
        System.out.println(count);
    }
    public static void DFS(int v){

        Stack<Integer> stack = new Stack<Integer>();
        stack.push(v); // 스택에 넣기
        visited[v] = true; // 방문 안했으면 방문 표시
        while(!stack.isEmpty()){ // 스택이 비어질때 까지
            int num = stack.pop(); // 꺼내기

            for(int i : arr[num]){ // 꺼낸 공간에 연결된 연결리스트를 순회
                if(!visited[i]){ // 방문 안했으면
                    stack.push(i); // 스택에 넣고
                    visited[i] = true; // 방문 표시
                }
            }
        }
    }
}

코드 with 인접 행렬

import java.util.*;
import java.io.*;
public class Baek11724withArray {
    public static int arr[][];
    public static boolean visited[]; // 방문 여부 배열
    public static int n; // 크기 전역 변수로 빼기
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        visited = new boolean[n+1];
        arr = new int[n+1][n+1];

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            // 무방향 그래프 특성
            arr[start][end] = 1;
            arr[end][start] = 1;
        }

        int count = 0;
        for(int i = 1; i < n+1;i++){
            if(!visited[i]){ // 방문 안했으면
                count++; // 처음 DFS 시작할때 +1
                DFS(i); // DFS 시작
            }
        }
        System.out.println(count);
    }
    public static void DFS(int v){
        if(visited[v]) return; // 이미 방문했으면 pass
        visited[v] = true; // 방문 안했으면 방문 표시
        for(int i = 1; i < n+1; i++){
            if(arr[v][i] == 1){ // 1이면 연결 되있다는 의미
                DFS(i);
            }
        }
    }
}

인접 행렬

• 주 정점을 연결하는 간선을 조회할 때 O(1), 정점(i)의 차수를 구할 때 O(N)
• 메모리 공간 낭비, 모든 간선의 수 알아낼 때 O(N^2)

인접 리스트

• 메모리 효율적, 모든 간선의 수 알아낼 때 O(N+E)
• 두 정점을 연결하는 간선 조회나 정점의 차수 알아낼 때 O(degree(V))

상황에 따라 최선의 방법으로!!