알고리즘 풀이 - 백준 13023(ABCDE, 그래프(DFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

친구 관계가 주어질 때, A-B-C-D-E와 같은 관계가 있으면 1을, 없으면 0을 출력하는 문제

 

 

2. 풀이

 

DFS, BFS 등의 그래프 탐색을 통해 친구 관계가 어떻게 이어지는 지 확인하면 된다.

A-B-C-D-E와 같은 관계를 찾는 다는 것은 그와 같이 5명이 서로 친구 관계인 경우를 찾으면 된다는 것이다.

 

따라서 탐색 과정에서 그러한 관계를 찾으면 1을 출력하고 모두 다 탐색이 완료되었음에도 그러한 관계가 없다면 0을 출력한다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

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

public class Main{
    static int n;
    static int m;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static int ans = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n];
        visited = new boolean[n];

        for(int i=0; i < n; i++){
            graph[i] = new ArrayList();
        }
        for(int i=0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            // 양 방향 친구 관계이므로 아래와 같이 추가
            graph[start].add(end);
            graph[end].add(start);
        }

        // 시작점을 모두 체크해야 한다.
        for(int i=0; i < n; i++){
            if(ans == 0){
                dfs(i, 1);
            }
        }
        bw.write(String.valueOf(ans));
        bw.flush();
        br.close();
    }

    private static void dfs(int curr, int depth){
        // 연속으로 5명째 이어진 경우라면 구하고자 하는 관계임
        if(depth == 5){
            ans = 1;
            return;
        }

        // 중복 탐색 되지 않도록 탐색 완료 표시를 한다.
        visited[curr] = true;
        for(int f : graph[curr]){
            if(!visited[f]){
                dfs(f, depth+1);
            }
        }
        // 다른 곳에서 다시 탐색을 시작할 때, 다시 탐색이 가능하도록 false로 다시 지정
        visited[curr] = false;
    }
}

 

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.