[BAEKJOON] 13023. ABCDE(JAVA)

:D 문제

---

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

Baekjoon

13023번: ABCDE

 

:D 풀이 방법

---

먼저, 입력된 사람들의 관계를 리스트로 저장해두었다. 그리고 모든 사람에 대해 DFS탐색을 진행하였다.

현재 기준인 사람을 시작으로 정하고 4개의 관계가 만들어질 때까지 탐색을 진행한다. 이 때, 관계가 4개 이상 나오지 않는 경우는 방문 여부를 해제하여 주는 작업을 해주어야 한다. 그래야 다음 경우를 제대로 탐색할 수 있다.

 // dfs 탐색
    private static void dfs(int current, int cnt) {

        if (cnt == 4) {
            answer = true;
            return;
        }

        visited[current] = true;

        for (int v : friends.get(current)) {
            if (visited[v]) continue;
            dfs(v, cnt + 1);
        }
        // 방문 노드 해제 - 안되는 경우 다시 해제
        visited[current] = false;
    }

 

 

:D 작성 코드

---

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 Solution13023H {

    static int N, M;
    static List<List<Integer>> friends;
    static boolean[] visited;
    static boolean answer;

    public static void main(String[] args) throws IOException {

        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        StringTokenizer tokenizer = new StringTokenizer(input, " ");
        N = Integer.parseInt(tokenizer.nextToken());
        M = Integer.parseInt(tokenizer.nextToken());
        friends = new ArrayList<>();

        // 사람 수만큼 생성
        for (int i = 0; i < N; i++) {
            friends.add(new ArrayList<>());
        }

        // 친구 관계 저장
        for (int i = 0; i < M; i++) {
            input = br.readLine();
            tokenizer = new StringTokenizer(input, " ");
            int friendA = Integer.parseInt(tokenizer.nextToken());
            int friendB = Integer.parseInt(tokenizer.nextToken());

            // 서로 친구 관계
            friends.get(friendA).add(friendB);
            friends.get(friendB).add(friendA);
        }

        // 모든 범위 탐색
        for (int i = 0; i < N; i++) {
            if(answer) break;
            visited = new boolean[N];
            dfs(i, 0);
        }
        System.out.println(answer? 1 : 0);
    }

    // dfs 탐색
    private static void dfs(int current, int cnt) {

        if (cnt == 4) {
            answer = true;
            return;
        }

        visited[current] = true;

        for (int v : friends.get(current)) {
            if (visited[v]) continue;
            dfs(v, cnt + 1);
        }
        // 방문 노드 해제 - 안되는 경우 다시 해제
        visited[current] = false;
    }
}