[BOJ] 13023.ABCDE(DFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

처음에 문제 이해를 잘못하고 풀고 있었다...

`일부 사람들`이 ABCDE와 같은 관계를 가지고 있다면

위와 같은 친구 관계에 해당한다.

한 마디로 큰 무리에서 5명의 친구로 이루어진 작은 무리(?)가 있는지 확인하는 것이다.

즉 깊이가 5인 경우가 있는지!

실수했던 부분은 visited 처리인데

만일, 0번부터 출발해서 탐색으로 도달한 깊이가 4일 때,

다른 길로 깊이가 5인 길이 있을 수 있다.

하지만 깊이가 4인 길을 가면서 visited true 를 해준 상태라서

다른 길을 갈 때는 이미 확인한 길이라서 pass 해버리게 된다.

그래서 다른 길로 갈 경우도 확인해주기 위해 돌아갈 때는 visited false 처리를 해주어야 한다.

반례 예)

먼저 0 - 1 - 3 - 4 로 탐색을 시도해보고,

0 - 1 - 2 - 3 - 4 로 탐색을 시도해볼 때,

이미 3, 4번은 visited true 상태라서 

돌아갈 때는 visited false 처리를 해주기 !!

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer;   public class BOJ13023 {       static int N, M, res;     static ArrayList<Integer>[] friends;     static boolean visited[];          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());                  N = Integer.parseInt(st.nextToken());         M = Integer.parseInt(st.nextToken());         friends = new ArrayList[N];         for (int i = 0; i < N; i++) {             friends[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());                          friends[a].add(b);             friends[b].add(a);                     }         // 0번 친구부터 확인         for (int i = 0; i < N; i++) {                          visited = new boolean[N];             visited[i] = true;             process(i, 0);             // 위와 같은 관계 발견 시             if(res == 4) break;         }                  if(res == 4) System.out.println(1);         else System.out.println(0);     }       private static void process(int my, int cnt) {                  res = Math.max(res, cnt);         // 위와 같은 관계 발견 시         if(res == 4) return;                  for (int frd : friends[my]) {             if(visited[frd]) continue;             visited[frd] = true;             process(frd, cnt + 1);         }         // 다른 경로에서도 확인할 수 있도록         visited[my] = false;     }   } Colored by Color Scripter

cs