[백준/JAVA] 13023번: ABCDE

🔺 문제

13023번: ABCDE

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static ArrayList<Integer>[] A;  // 그래프 데이터 저장 인접 리스트
    static boolean[] visited;       // 방문 배열
    static boolean arrive;          // 🔔 도착 여부
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        A = new ArrayList[N];
        for(int i = 0 ; i < N ; i++) {
            A[i] = new ArrayList<>();
        }
        visited = new boolean[N];
        arrive = false;
        
        // 인접 리스트 초기화
        while(M -- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            A[a].add(b);
            A[b].add(a);
        }
        
        // 🎈 각 점에 대해  dfs 수행 🎈
        for(int i = 0 ; i < N ; i++) {
            dfs(i, 1);  // depth 1부터 시작
            
            if(arrive)
                break;
        }
        
        System.out.println(arrive ? 1 : 0);
    }
    
    private static void dfs(int now, int depth) {
        // 종료 조건 : depth가 5가 되었을 때
        if(depth == 5 || arrive) {
            arrive = true;
            return;
        }
        
        visited[now] = true;
        for(int next : A[now]) {
            if(!visited[next]) {
                dfs(next, depth + 1);   // 재귀 호출 돌 때마다 1씩 증가
            }
        }
        visited[now] = false;   // 🔔 백트래킹 🔔 (now 노드의 모든 인접 노드들 방문 후, now 노드를 다시 방문할 수 있도록)
    }
}

✅ 해결 아이디어
- DFS
- DFS 수행할 때, 재귀 호출마다 깊이를 더함. (깊이가 5 이상이면 1 / 아니면 0 출력)
- visited[now] = false; : 현재 노드 now 방문 후, 해당 노드를 다시 방문 가능한 상태로 되돌리기 위해 사용

 

⇨ 52~57번째 줄을 이렇게 써도 된다.

for(int i : A[now]) {
    if(!visited[i]) {
        visited[now] = true;
        DFS(i, depth + 1);  // 재귀 호출 돌 때마다 depth 1씩 증가
        visited[now] = false;
    }
}

 

 

 

---

🔺 다른 풀이들

- 풀이1) 자세한 설명,,,,굿

[백준 - Java] 13023번 : ABCDE

친절한 설명 너무너무 감사합니다ㅠㅠㅠ

 

 

- 풀이2) DFS 호출 횟수로 판단

[백준] 13023. ABCDE (Java)

DFS 호출 횟수가 4 이상(=5개의 노드가 연속되게 존재)이면 리턴하게 했고,

DFS for문 안의 if문 안에 visited[i] = false; 코드도 함께 넣어주셨다.

 

---

💬 느낀 점

🔶 연결 요소 갯수 / 재귀 깊이 → DFS 수행 횟수와 연관 有

 

 

1회독	2회독	3회독	4회독	5회독
V	6.15	8.30

 

(+ 3회독 : 8.30)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    
    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(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        A = new ArrayList[N];
        for(int i = 0 ; i < N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        visited = new boolean[N];
        flag = false;
        
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            A[a].add(b);
            A[b].add(a);
        }
        
        for(int i = 0 ; i < N ; i++) { // 모든 점에 대해 DFS 수행
            dfs(i, 1);
            
            if(flag) break;
        }
        
        System.out.println(flag ? 1 : 0);
    }
    
    private static void dfs(int startIdx, int depth) {
        // 종료  조건
        if(depth == 5 || flag) {
            flag = true;
            return;
        }
        
        visited[startIdx] = true;
        
        for(int next : A[startIdx]) {
            if(!visited[next]) {
                dfs(next, depth + 1);
            }
        }
        
        visited[startIdx] = false;
    }
}