[Gold V] ABCDE - 13023 (Java)

 

문제 링크

성능 요약

메모리: 205512 KB, 시간: 456 ms

 

분류

백트래킹, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

 

문제 설명

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을 출력한다.

 

풀이 (DFS)

시간 복잡도 O(N) 공간 복잡도 O(N)

아이디어: 문제에서는 A-B-C-D-E의 관계가 존재하는지 묻고 있기에 이는 곧 그래프 정보에서 깊이가 5인 구간이 존재하는지 여부를 묻는 다고 볼 수 있다. 따라서 DFS(깊이 우선 탐색)을 사용하여 만약 5이상의 깊이를 가지는 구간이 존재한다면 1을 출력시키고 프로그램을 종료시키면 된다.

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

public class Main {
    static HashMap<Integer, ArrayList<Integer>> map;
    static boolean[] visited;
    static int depth;
    public static boolean dfs(int node){
        depth++;
        // 깊이가 5이면 문제에서 원하는 관계가 존재하기에 true
        if(depth ==5) return true;
        // 현재 노드를 방문한 것으로 표시
        visited[node] = true;

        // 현재 노드에 인접한 모든 노드를 확인
        ArrayList<Integer> nextNodes = map.get(node);
        for (Integer nextNode : nextNodes) {
            if(!visited[nextNode])
                if(dfs(nextNode))
                    return true;
        }
        // 깊이 감소
        depth--;
        visited[node] = false; // 방문 초기화
        return false;
    }
    public static int sti(StringTokenizer st){
        return Integer.parseInt(st.nextToken());
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = sti(st), M = sti(st);
        map = new HashMap<>();
        for (int i = 0; i < N; i++) map.put(i,new ArrayList<>());
        boolean ans = false;

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int op1 = sti(st), op2 = sti(st);
            // 같은 관계는 두번 이상 주어지지 않는다.
            map.get(op1).add(op2);
            map.get(op2).add(op1);
        }
        // 깊이가 5면 1 아니면 0
        for (int i = 0; i < N; i++) {
            visited = new boolean[N];
            depth = 0;
            if (dfs(i)) {
                System.out.println(1);
                return;
            }
        }
        System.out.println(0);
    }
}

참고하여 개선된 풀이 (DFS)

아이디어: static HashMap<Integer, ArrayList<Integer>> map; 자료구조를 단순한 연결 리스트 형식의 자료구조로 변경함으로써 버킷배열, 해시 함수, 재해시 연산을 줄임으로서 오버헤드를 줄여 메모리와 속도를 둘다 개선

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

public class Main {
    static int answer = 0;
    static boolean[] visited;
    static Node[] map;
    static class Node{
        int vertex;
        Node link;

        public Node(int vertex, Node link) {
            this.vertex = vertex;
            this.link = link;
        }
    }
    static void dfs(int index, int depth){
        visited[index] = true;
        if(depth==5){
            answer =1;
            return;
        }
        for(Node next = map[index]; next!=null; next=next.link){
            if(!visited[next.vertex])
                dfs(next.vertex,depth+1);
        }
        visited[index] = false;
    }
    public static int parseTokenToInt(StringTokenizer st){
        return Integer.parseInt(st.nextToken());
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N =  parseTokenToInt(st), M =  parseTokenToInt(st);
        map = new Node[N];
        visited = new boolean[N];
        int head, next;

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            head =  parseTokenToInt(st);
            next =  parseTokenToInt(st);
            // 같은 관계는 두번 이상 주어지지 않는다.
            map[head] = new Node(next, map[head]);
            map[next] = new Node(head,map[next]);
        }
        // 깊이가 5면 1 아니면 0
        for (int i = 0; i < N; i++) {
            dfs(i,1);
        }
        System.out.println(answer);
    }
}