[G5] ABCDE : Java : 13023 - DFS

문제

13023번: ABCDE

 

 

 

 

풀이 과정

문제의 조건을 봤을 때 A-B-C-D-E 인 관계를 찾으면 되는거라서 탐색을 했을 때 깊이 5까지 파고드는 관계를 찾으면 된다고 생각했다.

그래서 DFS를 이용하였고, 재귀함수를 호출할 때마다 깊이를 1씩 더해주어 깊이가 5가 됐을 때, '찾았다' 라고 표시했다.

 

하지만 '틀렸습니다.'만 떴다! ㅠ 아직 갈 갈이 멀다. 답이랑 비교했을 때 틀린 점은 2가지가 있었다.

틀린이유 1 : 탐색의 시작을 0번째만 하려고 했다는 것.  

// 내가 짠 코드
DFS(0, 1);
 
// 답
for(int i=0; i<n; i++){
            DFS(i, 1);
            visited = new boolean [n];

            if(result)
                break;
}

DFS를 배웠을 때 0번째 노드를 시작으로만 탐색을 진행해서 그 외의 노드를 시작 기준으로 탐색을 생각하지 못했다. 시작 노드에 따라 결과가 달라지는 것을 알았지만 전체 노드를 탐색할 생각을 안하고 재귀 함수의 알고리즘을 고칠 생각만 했다. 다음부터는 시간 복잡도를 구한 다음 전체를 탐색해도 문제가 없는지를 확인하자!

 

 

틀린 이유2 : 방문이 끝나고 방문노드를 false 할 생각을 못한 것. 

  // 답 코드
  static void DFS(int v, int count){
        if(count == 5 || result){
            result = true;
            return;
        }

        if(visited[v])
            return;

        visited[v] = true;
        for(int i : A[v]){
            if(!visited[i]){
                DFS(i, count+1);
            }

        }
        /* 생각 못한 부분 */
        visited[v] = false; //이어지는 관계를 조사해야 하기 때문에 다시 돌아왔을 떄 방문 했던 노드라고 검색을
        // 안하면 안되고 옆에 붙이기(친구 관계)를 위해서는 다시 방문을 안했다고 해야 조사를 할 수 있음
    }

내가 풀었을 때 문제점은 친구 관계가 되어 있지만 이미 방문 했던 노드라서 더 이상 방문을 하지 않아 깊이가 더 깊어지지 않았다. 사실 답 코드를 보고도 왜 저기에 false를 하는지 완전히 이해하지 못했다.  원리는 알겠는데 false를 했을 때 어디 조사 시점에 영향이 가고, 탐색을 진행 했을 때 또 다른 영향은 없는지를 파악하지 못했다... 아무튼 쉬운 문제인 줄 알고 막 덤볐는데 역시 골드랄까..?

 

 

 

 

전체 코드 - Java

import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringTokenizer;


public class Main {

    static ArrayList<Integer>[] A;
    static boolean [] visited;
    static boolean result = false;
    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 e = Integer.parseInt(st.nextToken()); // 간선의 수

        A = new  ArrayList[n];
        visited = new boolean [n];

        // node
        for(int i=0; i<n; i++){
            A[i] = new ArrayList<Integer>();
        }

        // edge
        for(int i=0; i<e; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            // 관계 추가
            A[u].add(v);
            A[v].add(u);
        }

        int count = 1;
        for(int i=0; i<n; i++){
            DFS(i, 1);
            visited = new boolean [n];

            if(result)
                break;
        }

       // DFS(0, 1);
        if(result){
            System.out.println("1");
        }
        else {
            System.out.println("0");
        }

    }

    static void DFS(int v, int count){
       // System.out.println(count);
        if(count == 5 || result){
            result = true;
            return;
        }

        if(visited[v])
            return;

        visited[v] = true;
        for(int i : A[v]){
            if(!visited[i]){
                DFS(i, count+1);
            }

        }
        visited[v] = false; //이어지는 관계를 조사해야 하기 때문에 다시 돌아왔을 떄 방문 했던 노드라고 검색을
        // 안하면 안되고 옆에 붙이기(친구 관계)를 위해서는 다시 방문을 안했다고 해야 조사를 할 수 있음
    }




}