[백준] 13023번: ABCDE (Java)

1. 문제설명

N명의 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

친구 관계가 주어질 때, 조건에 맞는 친구 관계가 존재하는지 구하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 512MB

 

2. 접근 방식

• 인접 리스트 형태로 친구 관계를 저장한다.
• DFS를 사용해 각 노드로부터 시작해서 5명의 친구 관계가 나올 수 있는지 확인한다.
• DFS에서 방문한 노드를 확인하기 위해 `visited` 배열을 사용한다.
  이때 DFS를 호출하고 난 후, 방문 처리한 것을 되돌린다. (백트래킹)

 

3. 틀린 이유

인접 행렬을 사용해서 “시간 초과”가 나왔다.

⇒ 인접 리스트를 사용하는 방식을 사용했다.

 

4. 최종 코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, m; // 친구 수, 친구 관계 수
    static List<Integer>[] friend; // 친구 관계 저장하는 인접리스트
    static boolean[] visited; // 방문 여부 확인하는 배열
    static boolean possible; // 5명의 친구 관계가 가능한지 확인

    static void dfs(int s, int depth) {
        if(depth == 5) { // 친구 관계 5명이 나오면
            possible = true;
            return; // 종료
        }

        for(int next : friend[s]) { // 인접한 노드 탐색
            if(!visited[next]) { // 아직 방문하지 않은 노드라면
                visited[next] = true; // 해당 노드 방문 처리
                dfs(next, depth+1); // 해당 노드를 다음 깊이로 재귀 호출
                visited[next] = false; // 방문 처리 취소 (백트래킹)
            }
        }
    }

    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());
        friend = new ArrayList[n];
        for(int i=0; i<n; i++) { // 인접 리스트 초기화
            friend[i] = new ArrayList<>();
        }
        visited = new boolean[n];
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            // 양방향으로 친구 관계 저장
            friend[a].add(b);
            friend[b].add(a);
        }

        for(int i=0; i<n; i++) { // 모든 노트를 탐색
            visited[i] = true; // 시작 노드 방문 처리
            dfs(i, 1); // 깊이 1로 탐색 시작
            visited[i] = false; // 시작 노드 방문 처리 취소

            if(possible) break; // 5명의 친구 관게를 찾을 경우 종료
        }

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