공부 182일차: 백준 13023번 ABCDE 자바 java

13023 ABCDE

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

13023번: ABCDE

 

 

 

---

백준 13023번 문제 ABCDE

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	29208	9050	6015	28.693%

문제

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

제한

 

예제 입력 1

5 4
0 1
1 2
2 3
3 4

예제 출력 1

1

예제 입력 2

5 5
0 1
1 2
2 3
3 0
1 4

예제 출력 2

1

예제 입력 3

6 5
0 1
0 2
0 3
0 4
0 5

예제 출력 3

0

예제 입력 4

8 8
1 7
3 7
4 7
3 4
4 6
3 5
0 4
2 7

예제 출력 4

1

힌트

 

 

 

 

---

과정 생각해보기 & 오답

---

 

문제의 A, B, C, D, E와 같은 관계라는 말은 다음과 같다

이렇게 한 노드에서 출발했을 때 건너건너 친구이면 된다

그래프의 모든 노드를 탐색하는 DFS를 이용해 깊이가 4면 조건을 만족시키는 것이 된다

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, m, check;
    static boolean[] visited;
    static ArrayList<Integer>[] list;    // 연결리스트
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        visited = new boolean[n];
        list = new ArrayList[n];
        for(int i = 0; i < n; i++) {
            list[i] = new ArrayList<Integer>();
        }
        
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            // 양방향 (x가 y랑 친구면 y도 x랑 친구)
            list[x].add(y);
            list[y].add(x);
        }
        
        for(int i = 0; i < n; i++) {
            DFS(i, 0);
            
            if(check == 1) {    // 이미 노드끼리 연결된 거 확인했으면
                break;            // 반복문 종료
            }
        }
        bw.write(check+"");
        bw.flush();
        bw.close();
    }
    
    static void DFS(int a, int depth){
        if(depth == 4) {    // 연결되어 있으면
            check = 1;
            return;
        }
        visited[a] = true;    // 방문 처리
        
        for(int val : list[a]) {
            if(!visited[val]) {
                DFS(val, depth+1);
            }
        }
        visited[a] = false;    // 다른 list에서 a와 연결되어있을 수 있으므로 초기화
    }
 
} 

 

 

 

---