[백준] 11724번 연결 요소의 개수 - DFS방식 / 재귀 함수 이용/ 무방향 그래프

문제

 

 

My Code

import java.io.*;
import java.util.LinkedList;
import java.util.Stack;


public class Main {
    static LinkedList<Integer>[] linkedList;
    static Stack<Integer> stack;
    static int[] result;
    static int index = 0;
    static boolean[] tf;
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int[] input = new int[2];
        stack = new Stack<>();
        int count = 0;

        //정점과 간선 입력&저장
        String str = bf.readLine();
        int n = Integer.parseInt(str.split(" ")[0]);
        int m = Integer.parseInt(str.split(" ")[1]);
=
        //결과 배열 선언
        result = new int[n+1];

        //true, false판별 배열&인접 리스트 생성 및 초기화
        tf = new boolean[n+1];
        linkedList = new LinkedList[n+1];
        for(int i = 0; i < n+1; i++) {
            linkedList[i] = new LinkedList<>();
            tf[i] = false;
        }

        //간선의 양 끝 점 u, v입력&저장
        for (int i = 0; i < m; i++) {
            String str2 = bf.readLine();
            int u = Integer.parseInt(str2.split(" ")[0]);
            int v = Integer.parseInt(str2.split(" ")[1]);
            if(u==v) return;
            addEdge(u, v); //인접 리스트에 u, v 저장
        }

        //true, false판별
        for (int i = 1; i < linkedList.length; i++){
            if(tfDivide(i) == 0) continue;
            else {
                tfDivide(i);
                count += 1;
            }
        }

        System.out.println(count);
    }

    private static int tfDivide(int i) {
        //false는 한번도 스택에 저장하지 않은 값 -> 결과 배열에 값 저장
        if (tf[i] == false) {
            stack.push(i);
            tf[i] = true;
            result[index] = stack.pop();
            index++;
            for (int j = 0; j < linkedList[i].size(); j++)
                tfDivide(linkedList[i].get(j));
            return 1;
        }
        else{
            return 0;
        }
    }

    //인접 노드 더하기
    private static void addEdge(int u, int v) {
        linkedList[u].add(v);
    }
}

 

 

문제의 핵심 & 알게된 점

우선 내 코드로 출력은 가능한데 틀렸습니다라고 계속 떴다.

여러 문제가 있었다.

1. 

for (int i = 0; i < m; i++) {
    String str2 = bf.readLine();
    int u = Integer.parseInt(str2.split(" ")[0]);
    int v = Integer.parseInt(str2.split(" ")[1]);
    if(u==v) return;
    addEdge(u, v); //인접 리스트에 u, v 저장
}

여기서 

addEdge(u, v); //인접 리스트에 u, v 저장

 

인접 리스트에 값을 더하는 과정에서 문제가 있었다.

문제는 방향이 없는 그래프가 주어졌다고 했다.

즉, 간선은 두 정점 간의 양방향 연결을 나타내야 하고, 양쪽 방향으로 연결을 표시해야 한다.

한쪽 방향으로만 하면 방향이 있는 그래프가 되기 때문이다.

그래서 addEdge(v, u);를 추가해야한다.

 

2.

for (int i = 1; i < linkedList.length; i++){
    if(tfDivide(i) == 0) continue;
    else {
        tfDivide(i);
        count += 1;
    }
}

if문으로 tfDivide()를 호출하고, 그 후 if문 안의 실행문에서도 tfDivide()를 호출한다.

따라서 중복 호출이 발생한다.

그래서 if문 안의 조건을 !tf[i]로 바꿨다.(함수 호출 없이 t, f판별)

 

3.

private static int tfDivide(int i) {
    //false는 한번도 스택에 저장하지 않은 값 -> 결과 배열에 값 저장
    if (tf[i] == false) {
        stack.push(i);
        tf[i] = true;
        result[index] = stack.pop();
        index++;
        for (int j = 0; j < linkedList[i].size(); j++)
            tfDivide(linkedList[i].get(j));
        return 1;
    }
    else{
        return 0;
    }
}

이 함수에서 tf를 판별할 필요는 없다. 위의 if문에서 했기 때문이고 그게 더 효율적이다.

stack은 dfs를 구현하기 위해 사용한 것인데 이 문제에서는 굳이 stack과 result[]를 이용하지 않아도 되서 지웠다.

for (int j = 0; j < linkedList[i].size(); j++)
    tfDivide(linkedList[i].get(j));

여기서 바로 tfDivide()를 호출하면 t,f판별이 되지 않기 때문에 if문을 통해 t,f판별을 해야한다.
그리고 이 반복문을 가독성이 높게 수정했다.
for each반복문을 이용했다.

 

참고로

tf = new boolean[n+1];
linkedList = new LinkedList[n+1];
for(int i = 0; i < n+1; i++) {
    linkedList[i] = new LinkedList<>();
    tf[i] = false;
}

여기서 tf[i] = false;

는 굳이 없어도 되는 코드다.

이미 선언하면 default 값이 false이기 때문이다.

 

이와 같은 여러 문제를 고쳐서 밑의 코드로 수정하니 맞았습니다라고 떴다.

힘든 과정이었다...

 

 

수정한 Code

import java.io.*;
import java.util.LinkedList;
import java.util.Stack;


public class Main {
    static LinkedList<Integer>[] linkedList;
    static boolean[] tf;
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        //정점과 간선 입력&저장
        String str = bf.readLine();
        int n = Integer.parseInt(str.split(" ")[0]);
        int m = Integer.parseInt(str.split(" ")[1]);


        //true, false판별 배열&인접 리스트 생성 및 초기화
        tf = new boolean[n+1];
        linkedList = new LinkedList[n+1];
        for(int i = 0; i < n+1; i++) {
            linkedList[i] = new LinkedList<>();
        }

        //간선의 양 끝 점 u, v입력&저장
        for (int i = 0; i < m; i++) {
            String str2 = bf.readLine();
            int u = Integer.parseInt(str2.split(" ")[0]);
            int v = Integer.parseInt(str2.split(" ")[1]);
            addEdge(u, v);
            addEdge(v, u);
        }

        //true, false판별 및 함수 호출
        int count = 0;
        for (int i = 1; i < linkedList.length; i++){
            if(!tf[i]) {
                tfDivide(i);
                count++;
            }
        }
        System.out.println(count);
    }

    //dfs방식 함수
    private static void tfDivide(int i) {
        tf[i] = true;
        for (int j : linkedList[i]){
            if (!tf[j])tfDivide(j);
        }
    }

    //인접 노드 더하기
    private static void addEdge(int u, int v) {
        linkedList[u].add(v);
    }
}