[JAVA][Baekjoon] 13023번 ABCDE 🌟🌟

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

---

📌 접근 방식

N명의 사람들이 있는데, 이들 중 5명이 다음과 같은 조건으로 연결되어 있는지 확인하는 문제

1. A는 B와 친구다.
2. B는 C와 친구다.
3. C는 D와 친구다.
4. D는 E와 친구다.

즉, 깊이가 5인 친구 관계를 찾으면 됨

그래서 DFS(깊이 우선 탐색) 을 사용했습니다.

 

🔑 핵심 아이디어

• DFS로 탐색하면서 깊이가 5가 되는 순간이 있다면 조건을 만족한다고 볼 수 있음
• 방문한 노드를 다시 방문하지 않도록 모든 노드에 대해 탐색을 진행

 

[알고리즘] 깊이 우선 탐색 : DFS(Depth-First-Search)

 

---

✅ PASS CODE

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

public class Main {
    public static boolean []visited;
    public static ArrayList<Integer> []A;
    public 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());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        A = new ArrayList[N];
        visited = new boolean[N];

        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);
        }
        for(int i=0; i<N; i++) {
            DFS(i, 1);
            if(arrive) {
                break;
            }
        }
        if(arrive) {
            System.out.println("1");
        } else {
            System.out.println("0");
        }
    }
    public static void DFS(int now, int depth) {
        if(depth == 5 || arrive) {
            arrive = true;
            return;
        }
        visited[now] = true;
        for(int i : A[now]) {
            if(!visited[i]) {
                DFS(i, depth+1);
            }
        }
        visited[now] = false;
    }
}

 

🔑 핵심 포인트

 

• DFS와 백트래킹
  • DFS로 깊이 탐색하면서 조건에 맞는 경로를 찾는다.
  • 탐색 후에는 visited 상태를 초기화하여 다른 경로 탐색이 가능하도록 함.
• 최적화
  • depth == 5인 순간 바로 종료

 

😊 느낀 점

이번 문제를 풀면서 DFS(깊이 우선 탐색)을 확실히 익힐 수 있었다. 깊이로 조건을 확인하며 탐색을 종료하고 불필요한 계산을 하지 않는 것이 매우 효율적이라는 점을 느꼈다!

DFS 유형의 문제를 여러 번 풀어보니까 점점 익숙해져 가는 것 같다!!🔥