[BaekJoon] 13023번 ABCDE (Java) 문제 풀이 [Gold 5]

문제

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

13023번: ABCDE

 

어떻게 풀 것인가?

DFS를 이용한 간단한 문제 풀이였다.

 

그래서는 이중연결리스트를 이용하여 연결된 친구사이를 표현한 뒤에 재귀를 이용한 DFS로 문제를 풀었으며 DFS를 통해서 노드를 쭉쭉 연결해 나아갔을때 status변수를 이용하여 만약 깊이가 5라면 true 그것이 아니라면 false를 반환하는 식으로 문제를 해결했다.

 

풀면서 놓쳤던점

그래프 탐색이라고 하면 항상 BFS만 이용하였기에 DFS는 익숙하지 않아서 애를 많이 먹었다.

 

이 문제를 통해 얻어갈 것

재귀를 이용한 DFS 문제 풀이

 

내 코드 

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

public class Main {

    static boolean status;
    static List<Integer>[] list;
    static boolean[] check;

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

        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 a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }

        status = false;
        for (int i = 0; i < n; i++) {
            check = new boolean[n];
            dfs(i, 1);
            if (status) {
                System.out.println(1);
                return;
            }
        }
        System.out.println(0);
    }

    static void dfs(int idx, int depth) {
        if (depth == 5) {
            status = true;
            return;
        }
        check[idx] = true;
        for (int nxt : list[idx]) {
            if (!check[nxt]) {
                dfs(nxt, depth + 1);
            }
        }
        check[idx] = false;
    }
}

 

참고

X