[백준] 13023 : ABCDE (JAVA)

문제

BOJ 13023 : ABCDE - https://www.acmicpc.net/problem/13023

풀이

친구관계라고 주어지지만, 이 관계를 가지고 그래프에 적용하면 된다.

입력받은 친구 관계를 각각의 인접리스트에 저장한다. 친구 관계는 양방향이기 때문에 양쪽 노드의 인접리스트에 저장한다. 사람 한명 한명을 node로 생각하고 주어지는 친구관계는 edge라고 생각하면, DFS탐색으로 인접한 노드들을 거쳐거쳐 5명이 이어지면 문제의 조건을 만족하게 된다.

시작점을 다르게하여 각각 dfs()를 호출했고, 한번이라도 5명이 이어졌다면 더 이상 진행하지 않고 1을 출력 후 종료했다.

코드

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

public class Main {

    static class Person{
        int idx;
        ArrayList<Person> adj;

        public Person(int idx) {
            this.idx = idx;
            this.adj = new ArrayList<>();
        }
    }
    
    static Person[] people;
    static boolean[] visited;
    static boolean flag;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");

        int n = Integer.parseInt(inputs[0]);
        int m = Integer.parseInt(inputs[1]);

        people = new Person[n];
        for(int i=0; i<n; i++){
            people[i] = new Person(i);
        }

        for(int i=0; i<m; i++){
            inputs = br.readLine().split(" ");

            int a = Integer.parseInt(inputs[0]);
            int b = Integer.parseInt(inputs[1]);

            people[a].adj.add(people[b]);
            people[b].adj.add(people[a]);
        }
        
        flag = false; 
        for(int i=0; i<n; i++){
            visited = new boolean[n];
            visited[i] = true;
            dfs(i, 1);
            if(flag) { // 5명이 이어진 경로가 있다면 1 출력 후 종료
                System.out.println(1);
                return;
            }
        }
        System.out.println(0);
    }

    public static void dfs(int now, int count){

        if(count==5){ // count는 이어진 사람의 수
            flag = true;
            return;
        }

        for(Person p : people[now].adj){
            if(!visited[p.idx]){
                visited[p.idx] = true;
                dfs(p.idx, count + 1);
                visited[p.idx] = false;
            }
        }

    }
}

정리

✔ 알고리즘 분류 - 그래프 이론, 그래프 탐색, 깊이 우선 탐색
✔ 난이도 - 🟡 Gold 5

🤦‍♀️ 오늘의 메모

• 골드 문제이지만 크게 어렵지 않았던 문제. 무언가 '관계'라는 게 주어지면 그래프를 생각할 것!

참고 사이트

딱히 없음