BOJ) ABCDE (13023 번)

ABCDE

13023번: ABCDE

 

문제 설명

 

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) 으로 주어지기 때문에, 최악의 상황이 아닌 경우의 불필요한 loop를 줄이기 위해 List를 선택해서 친구 관계를 저장해주었다.

 

문제를 처음 봤을 때는, 0 ~ N-1까지 모두 친구관계로 이어져야 하는 문제라고 생각해서 리턴 조건을 N-1로 설정했었다. 하지만, 문제에서 주어졌듯 5명의 관계만 존재하면 되는 문제라서 리턴 조건을 count == 5로 변경해주었고, 0에서 시작하는게 아니라 모든 번호에서 시작하도록 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 ABCDE_13023 {
  static final int MAX_COUNT =5;
  static boolean found;
  static List<Integer>[] friends;

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

    while(m-- >0) {
      st = new StringTokenizer(br.readLine());
      int left = Integer.parseInt(st.nextToken()), right = Integer.parseInt(st.nextToken());
      friends[left].add(right);
      friends[right].add(left);
    }

    br.close();
    solution(n);
  }

  private static void initFriends(int n) {
    friends = new ArrayList[n];
    for(int i=0; i<n; i++) {
      friends[i] = new ArrayList<>();
    }
  }

  private static void solution(int n) {
    for(int i=0; i<n; i++) {
      boolean[] visit = new boolean[n];
      dfs(i, 1, visit);
    }

    System.out.println(found ? '1' : '0');
  }

  private static void dfs(int now, int count, boolean[] visit) {
    if(count == MAX_COUNT) {
      found = true;
      return;
    }
    if(found) {
      return;
    }
    visit[now] = true;
    for(int friend : friends[now]) {
      if(!visit[friend]) {
        dfs(friend, count+1, visit);
      }
    }
    visit[now] = false;
  }
}