[java] 문제 025 (백준 13023)

문제

ABCDE

 

교재 풀이

import java.util.*;
public class P13023_친구관계파악하기 {
  static boolean visited[];
  static ArrayList<Integer>[] A;
  static boolean arrive;
  public static void main(String[] args) {
    int N; // 정점의 수
    int M; // 간선의 수
    arrive = false;
    Scanner scan = new Scanner(System.in);
    N = scan.nextInt();
    M = scan.nextInt();
    A = new ArrayList[N];
    visited = new boolean[N];
    for (int i = 0; i < N; i++) {
      A[i] = new ArrayList<Integer>();
    }
    for (int i = 0; i < M; i++) {
      int S = scan.nextInt();
      int E = scan.nextInt();
      A[S].add(E);
      A[E].add(S);
    }
    for (int i = 0; i < N; i++) {
      DFS(i, 1);
      if (arrive)
        break;
    }
    if (arrive)
      System.out.println("1");
    else
      System.out.println("0"); // 5의 깊이가 없다면 0 출력
  }
  public static void DFS(int now, int depth) { // DFS구현
    if (depth == 5 || arrive) { // 깊이가 5가되면 프로그램 종료
      arrive = true;
      return;
    }
    visited[now] = true;
    for (int i : A[now]) {
      if (!visited[i]) {
        DFS(i, depth + 1);
      }
    }
    visited[now] = false;
  }
}

 

내 풀이) 24.6.12에 풀고 7%에서 틀림

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

public class Main {
    static ArrayList<Integer>[] a;
    static boolean[] visited;
    static boolean flag;
    
	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());
        
        a=new ArrayList[n];
        visited=new boolean[n];
        flag=false;
        for(int i=0;i<n;i++){
            a[i]=new ArrayList<>();
        }
        
        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);
        }
        
        // 각 노드에 대해서라면 a[i]가 어레이리트스라서 인트로 못 받는다는 소리 
        // 그럼 향상된 for문으로? 해야 할까?
        // 그럼 이중 for문이 생각나는데 
        //     for i=0~n까지?
        //         for(int n:a[i])
        //     맞나? 
        //         i=2야, a[2]는 즉 노드 2와 연결된 노드들을 담은 배열이야 
        //         그 배열의 원소를 하나하나 향상된 for문으로 접근해서 하는 거지 
        //         그럼 시간 복잡도는 n 곱하기 ...
        //         m번 간선이 주어지니까 4000정도일가?
        //         그럼 2000 곱하기 4000인데 나쁘지 않나. 
        
        for(int i=0;i<n;i++){
            for(int now:a[i]){
                dfs(now,1); // depth가 1 
                
                if(flag==true){
                    break;
                }
            }
            
        }
        
        if(flag==true){
            System.out.println(1);
        }else{
            System.out.println(0);
        }
	}
	
	static void dfs(int node, int depth){
	    if(visited[node]==true){
	        return;
	    }
	    
	    if(depth==4){
	        flag=true;
	        return;
	    }
	    
	    visited[node]=true;
	    for(int now:a[node]){
	        if(visited[now]==false){
	            dfs(now,depth+1);
	        }
	    }
	}
}

// 왜 예제 입력 1이 0이 나오지. 
//     dfs(1, 1) -> dfs(0,2) -> dfs(2,2) -> dfs(3,3) -> dfs(4,4)
//     depth가 5가 아니라 4일 때 1을 출력해야 하나

//		총 N명이 참가하고 있다. 
//		    사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 
//		    일부 사람들은 친구이다.
//	    오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.
//            A는 B와 친구다.
//            B는 C와 친구다.
//            C는 D와 친구다.
//            D는 E와 친구다.
//        위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램
//        
//        첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)
//        둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다.
//            (0 ≤ a, b ≤ N-1, a ≠ b) 
//            같은 친구 관계가 두 번 이상 주어지는 경우는 없다.
//        문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력
//        
//        입력
//            5 4
//            0 1
//            1 2
//            2 3
//            3 4
//                5가 n, m이 4 
//        출력 => 1 
//        
//        접근법
//            교재 문제 분석 내용 보고 옴
//            각 노드에 대해 dfs를 수행해 줌.
//            이 때 abcde 관계를 재귀로 봄
//            즉 dfs(1)을 했는데 이 때 깊이가 5이상이 되면
//                1을 출력하고 
//                이런 경우가 없으면 0을 출력한다 
//        슈도코드 
//            인접리스트[] a 
//            방문배열 visited 
//            
//            n, m 입력받고 
//            인접리스트 배열 초기화해주고 
//            for m번 반복해서 
//                s,e: a,e를 여기에 받아서 서로 친구란 뜻 
//                a[s].add(e)
//                a[e].add(s)
//            
//            flag 변수: false로 초기화, -> 깊이 5 이상인 게 있다면 true, 아님 false로 되게끔
//            for 각 노드에 대해, 즉 n번 반복해서
//                각각 dfs를 수행해줌 
//                    그렇게 해서 어떤 노드에 대해 깊이가 5이상이면
//                    함수 내에서 flag를 true로 바꾸는 작업하면 됨
//                만약 flag가 true면 for문 그만 돌고 출력하고 끝내기 
//                
//            if flag가 false면  0 출력하기 
//            
//            dfs 구현  -> 인수로 노드 받고, 깊이 받고
//                시작 노드의 깊이가 1이라고 했을 때, 깊이가 5가 되면 flag 변수를 true로 만들기
//                
//                베이스 코드 
//                    없어도 되지 않나? 어차피 아래에서 방문 안 한 것만 재귀 호출할 텐데 
//                    일단 혹시 모르니까 방문한 노드일 경우 그냥 return으로 끝내자
//                    아님 또 깊이가 5가 되면 flag를 true로 해주는 것으로 하고 return
//                
//                핵심 로직 
//                    일단 visited에 방문했음을 체크하고 
//                    for 노드와 연결된 것들의 개수만큼 반복해서 
//                        if 연결된 노드(now)가 방문하지 않았다면 
//                            dfs(now, depth+1)

 

설명

        for(int i=0;i<n;i++){
            for(int now:a[i]){
                dfs(now,1); // depth가 1 
                
                if(flag==true){
                    break;
                }
            }
        }

=> 굳이 이렇게 할 필요 없고 그냥 교재처럼 하면 되는데. 

이걸 보고 예제들을 대입해보면서 잘못 흐름을 파악해서

 depth==4일 때 1이 출력되도록 수정했음

 

visited[node] = false; // 백트래킹

=> 교재에서 visited[now]=false한 부분을 넣어야 했음 

=> 백트래킹 해야 하는 까닭은 탐색 이론 설명에 있으니 참고