백준 13023번 - ABCDE / Java

문제

https://www.acmicpc.net/problem/13023

13023번: ABCDE

문제를 해석하면 그래프의 깊이가 4 이상인지 물어보는 문제이다. DFS로 탐색하면 된다

방문처리를 탐색이 끝나면 다시 false로 돌려주는 부분만 조심하면 어렵지 않다 

정점의 개수가 최대 2000개이므로 인접 행렬로 구현하면 메모리 낭비가 크므로 인접 리스트로 구현하는 것이 좋다.

 

알고리즘

1. 인접 리스트에 그래프를 저장한다

2. 재귀 방식으로 dfs를 실시한다. 파라미터에 깊이를 1씩 증가하면서 재귀 호출을 한다

3. 깊이가 4 이상이 되면 1, 탐색이 다 끝났는데 4 이상이 안되면 0을 출력한다

소스코드

/*
 * BOJ13023
 * 2020.01.23
 * Hyeonseong
 */
import java.util.*;
public class BOJ13023
{
    public static void main(String[] args) 
    {
        Solution s = new Solution();
    }
}
class Solution{
    int n; // 사람의 수
     int m; // 친구 관계의 수
    ArrayList<Integer>[] graph;
    boolean visit[];
     public Solution() {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        graph = new ArrayList[n];
        visit = new boolean[n];
        for(int i=0;i<n;i++) {
            graph[i] = new ArrayList<Integer>();
        }
        for(int i=0;i<m;i++) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            graph[a].add(b);
            graph[b].add(a);
        }
        for(int i=0;i<n;i++) {
            dfs(i,1); 
        }
        System.out.println("0"); // 종료가안됐으면 깊이가 부족한것이므로 0
    }
     public void dfs(int now, int cnt) { // 재귀 방식으로 탐색
         if(cnt==5) { // 깊이가 5가되면 출력하고 종료
             System.out.println("1");
             System.exit(0);
         }
         visit[now] = true;
         for(int i=0;i<graph[now].size();i++) {
             int next = graph[now].get(i);
             if(!visit[next]) {
                 dfs(next,cnt+1); 
             }
         }
         visit[now] = false; // 방문처리를 바꿔준다
     }
}