[백준 13023] 친구 관계 파악하기 (Java)

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

문제

BOJ 알고리즘 캠프에는 총 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을 출력한다.

예제 입력 1 복사

5 4
0 1
1 2
2 3
3 4

예제 출력 1 복사

1

 

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int E;
    static ArrayList<Integer>[] friend;
    static boolean[] visited; // DFS 방문여부
    static boolean found = false;

    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()); // 사람수 (노드 개수)
        E = Integer.parseInt(st.nextToken()); // 관계 개수 (엣지 개수)

        friend = new ArrayList[N]; // 사람 번호 0번부터 시작
        visited = new boolean[N];

        // 사람 수 만큼 인접 리스트 만들어줌
        for(int i=0; i<N; i++){
            friend[i] = new ArrayList<>();
        }

        // 관계 수(엣지) 만큼 for 순회하면서 관계 양방향 연결해주기
        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int human1 = Integer.parseInt(st.nextToken());
            int human2 = Integer.parseInt(st.nextToken());

            friend[human1].add(human2);
            friend[human2].add(human1);
        }

        for(int i=0; i<N; i++){
            if(!found){ // 관계를 찾은게 아니라면 탐색 1부터 시작
                DFS(i,1);
            }
        }

        System.out.println(found ? "1" : "0");
    }

    public static void DFS(int i, int depth){
        if(depth ==5){
            found = true;
            return;
        }

        if(visited[i]) return; // 만약 이미 방문한 노드라면

        // 아직 방문하지 않았으면 DFS 탐색 시작
        visited[i] = true;
        for(int other : friend[i]){
            // 해당 노드(사람)의 친구관계 탐색
            if(!visited[other]){
                DFS(other, depth + 1);
            }
        }
        visited[i] = false;
    }
}

 

DFS

• 모든 노드(0~N-1)를 돌면서 DFS 탐색을 수행.
• 깊이가 5가 되는 경로가 있으면 바로 1을 출력하고 종료.
• 중복 방문을 방지하기 위해 visited 배열을 사용.

DFS 탐색 흐름

1. 현재 노드를 방문했다고 체크.
2. 연결된 친구(인접 노드)로 이동 (재귀 호출).
3. 깊이가 5가 되면 종료하고 1 출력.
4. DFS 종료 후 원래 상태로 되돌리기 (백트래킹)