[백준] 13023번 - ABCDE [Java]

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

 

[백준] 13023번 - ABCDE [Java]

[백준] 13023번 - ABCDE [Java]

[백준] 13023번 - ABCDE [Java]

---

1.  아이디어

 

DFS 알고리즘으로 재귀 깊이 4가 되는 사람을 찾으면 조건에 맞는 친구관계를 찾게 되는 점을 이용했다.

---

2. 문제풀이

 

인접리스트를 활용한 DFS로 구현했고 탐색 과정에서 노드 가지에 대한 모든 탐색을 위해 방문 체크를 해제하는 로직을 설정했다. 최단 거리 BFS는 원형 연결 같은 케이스에서 오답이 나올 수 있어서 DFS를 통해 해결해야 했다.

---

3. 코드

 

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

public class Main {

    private static final List<List<Integer>> adj = new ArrayList<>();
    private static boolean[] visited;
    private static boolean flag = false;

    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());

        for (int i = 0; i < N; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            adj.get(A).add(B);
            adj.get(B).add(A);
        }

        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            if (flag) break;

            dfs(i, 0);
        }

        if (flag) System.out.println(1);
        else System.out.println(0);
    }

    private static void dfs(int node, int depth) {
        if (flag) return;

        if (depth == 4) {
            flag = true;
            return;
        }

        visited[node] = true;

        for (int next : adj.get(node)) {
            if (visited[next]) continue;

            dfs(next, depth + 1);
        }

        visited[node] = false;
    }

}

---

4. 후기