13023_ABCDE (JAVA)

13023번: ABCDE

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

public class Main {
    static int n;
    static boolean[] visited;
    static ArrayList<Integer>[] list;
    static boolean flag = false;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        visited = new boolean[n];
        int m = Integer.parseInt(st.nextToken());

		list = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            list[v1].add(v2);
            list[v2].add(v1);
        }

        for (int i = 0; i < n; i++) {
            if (!flag) {
                dfs(i, 1);
            } else break;
        }

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

    private static void dfs(int v, int depth) {
        if (depth == 5 || flag) {
            flag = true;
            return;
        }

        visited[v] = true;
        for (int i = 0; i < list[v].size(); i++) {
            if (!visited[list[v].get(i)]) {
                dfs(list[v].get(i), depth + 1);
            }
        }

        visited[v] = false;
    }
}

 

 

문제에서 원하는 조건은 "정점이 연속해서 5개가 연결되어 있는 경우" 이다.

 

그러므로, 각 정점에서 연결되어 있는 정점을 탐색하고 depth=5가 될 때 모든 탐색을 중단 + 1을 출력하면 된다.

depth=5 인 경우가 나오면 flag를 true로 바꾸어 표시하고, 나머지 탐색을 중단하도록 구현했다.

 

 

 

구현 내용을 단계별로 풀어 설명하면 다음과 같다.

 

1. 인접리스트 배열(ArrayList<Integer>[] list) 를 만들어, 정점 간의 연결 관계를 저장한다.

 

2. 모든 정점을 dfs함수로 돌린다.

     dfs(x)는 정점x과 연결관계에 있는 정점을 탐색하는 함수이다.

     이때, 연결된 정점으로 재귀를 돌릴 때 depth+1 하여 연결된 정점의 수를 표시한다.

 

     그리고, 한 정점에서 여러 개의 간선이 존재할 수 있으므로 (∵ 그래프)

     visited[v]를 true로 표시해서 dfs함수로 돌리고, 다시 visited[v]를 false로 바꾸어야 한다.

 

3. depth==5 는 '정점이 연속해서 5개가 연결되어 있는 경우'를 의미하고,

    문제에서 원하는 조건을 만족하는 것과 같으므로 flag=true로 변경하여 나머지 탐색을 모두 중단한다.

 

 

 

 

** 인접리스트 정리 참고!

그래프 - 인접행렬/인접리스트