코딩 테스트 [탐색] - 친구 관계 파악하기

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 이 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 여부를 구하는 프로그램을 작성하시오.

(시간 제한 2초)

---

입력

1번째 줄에 사람의 수 N(5 ≤ N ≤ 2,000)과 친구 관계의 수 M(1 ≤ M ≤ 2,000),
2번째 줄부터 M개의 줄에 정수 a와 b가 주어진다. a와 b는 친구라는 뜻이다(0 ≤ a, b ≤ N - 1, a ≠ b)
같은 친구 관계가 2번 이상 주어지지는 않는다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재할 때 1, 없으면 0을 출력한다.

예제 입력
8 8	// 노드 개수, 에지 개수
1 7
3 7
4 7
3 4
4 6
3 5
0 4
2 7

예제 출력
1

---

1단계 - 문제 분석하기

N의 최대 범위가 2,000이므로 알고리즘의 시간 복잡도를 고려할 때 좀 더 자유롭다.
문제에서 요구하는 A, B, C, D, E의 관계는 재귀 함수의 형태와 비슷하다. 주어진 모든 노드에 DFS를 수행하고 재귀의 깊이가 5이상(5개의 노드가 재귀 형태로 연결)이면 1, 아니면 0을 출력한다.
DFS의 시간 복잡도는 O(V + E)이므로 최대 4000, 모든 노드를 진행 했을 때 4,000 * 2,000, 즉, 8,000,000이므로 DFS를 사용해도 제한 시간 내에 문제를 풀 수 있다.

2단계 - 손으로 풀어 보기

1 그래프 데이터를 인접 리스트로 저장한다.

2 모든 노드에서 DFS를 수행한다. 수행할 때 재귀 호출마다 깊이를 더한다. 깊이가 5가 되면 1을 출력하고 프로그램을 종료한다.

3 모든 노드를 돌아도 1이 출력되지 않았다면 0을 출력한다.

3단계 - sudo코드 작성하기

N(노드 개수) M(에지 개수)
A(그래프 데이터 저장 인접 리스트)
visited(방문 기록 저장 배열)

for(N의 개수만큼 반복)
{
	A 인접 리스트의 각 ArrayList 초기화
}

for(M의 개수만큼 반복)
{
	A 인접 리스트에 그래프 데이터 저장
}

for(N의 개수만큼 반복)
{
	각 노드마다 DFS 실행
    if(arrive)
    	반복문 종료
}

if(arrive)
	1 출력
else
	0 출력
    
// DFS 구현하기
DFS(현재 노드, 깊이){
	if(깊이가 5 || arrive)
    {
    	arrive = true;
        함수 종료
    }
    
    방문 배열에 현재 노드 기록
    현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행(호출마다 depth 1씩 증가)
}

4단계 - 코드 구현하기

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

public class Q25 {
    static ArrayList<Integer>[] A;
    static boolean visited[];
    static Boolean arrive;

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

        arrive = false;

        A = new ArrayList[N];
        visited = new boolean[N];

        for(int i = 0; i < N; i++){
            A[i] = new ArrayList<Integer>();
        }

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            A[u].add(v);
            A[v].add(u);
        }

        for(int i = 0; i < N; i++){
            DFS(i, 1);
            if(arrive)
                break;
        }

        if(arrive)
            System.out.println("1");
        else
            System.out.println("0");
    }

    static void DFS(int v, int depth){
        if(depth == 5 || arrive){
            arrive = true;
            return;
        }

        visited[v] = true;

        for(int i : A[v]){
            if(!visited[i])
                DFS(i,depth+1);
        }

        visited[v] = false;
    }

}

---

• Do it! 알고리즘 코딩테스트 자바 편