[BaekJoon] #13023 ABCDE

문제이해

이 문제는 a - b - c - d - e 의 친구관계가 주어진 그래프에서 존재하는지 확인하는 문제입니다.

문제접근

DFS를 이용해 특정 깊이까지 도달할 수 있는 경로가 존재하는지 확인하고, 그 경로가 존재하면 1을, 존재하지 않으면 0을 출력해주면 됩니다.

노드마다 DFS를 수행해 얻은 도달 가능한 depth값은 다르기 때문에, 원하는 깊이의 경로가 존재하는지 확인하려면 모든 노드에 대해 DFS를 수행해주어야 합니다.

그러므로, main내부에서는 모든 노드를 시작점 삼아 DFS를 수행해주어야 합니다.

DFS 함수 내부에서는 원하는 깊이에 도달했을 경우 리턴해주고, 그렇지 않을 경우 방문하지 않은 인접정점에 대해서 DFS를 재귀호출주먼 됩니다.

DFS호출이 끝난 경우, visited 배열을 초기상태로 되돌려, main에서 그 다음 노드에 대해 DFS를 수행할 수 있게 해주면 됩니다.

문제포인트

1. 원하는 깊이의 관계가 그래프 상에서 존재하는가? -> 모든 노드에 대해 DFS 수행 + depth check
2. 모든 노드에 대해 DFS를 호출해주기 위해서는 DFS수행 이후, now node에 대해 방문배열 되돌려놓아야 함

인생 첫 골드에요

code

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

public class Main {
    static boolean visited[];
    static LinkedList<Integer>[] adjList;
    static boolean found = false; // 깊이 5를 찾았는지 여부 확인 변수
    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()); // 친구관계
        visited = new boolean[n];
        adjList = new LinkedList[n];

        for(int i=0; i<n ; i++){
            adjList[i] = new LinkedList<Integer>();
        }

        for(int i=0; i<m ; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            adjList[v1].add(v2);
            adjList[v2].add(v1);
        }
        for(int i=0; i<n; i++){
                DFS(i,1);
                if(found) break;
        }
        System.out.println(found? 1: 0 );

    }
    static void DFS(int i, int depth){
        if(depth == 5){
            found = true;
            return;
        }
        visited[i] = true;
        for(int t: adjList[i]){
            if(!visited[t]){
                DFS(t,depth+1);
                if(found) return;
            }
        }
        visited[i] = false;
    }
}