[BOJ] ABCDE

난이도 : Gold 5

문제 링크

 

1. 문제 설명

요구사항

• 모든 사람들의 친구관계가 주어질 때, 아래와 같은 친구관계가 존재하는지 판별하라.

 

친구관계

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

 

2. 내 풀이

• 5명의 사람이 연쇄적으로 친구인 관계 존재 여부

 

자료구조 (친구관계)

친구관계 : 양방향, 다대다, (친구 수)가변적

 

무방향 그래프

• Vertex: 사람, Edge: 친구

 

인접 리스트

• (메모리 관점에서) 자신의 친구들을 효율적으로 기억할 수 있음

 

코드

// 선언
private static List<List<Integer>> graph = new ArrayList<>();

// 초기화
for (int i = 0; i < nodeCnt; i++) {
    graph.add(new ArrayList<>());
}

// 친구관계 추가
for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    src = Integer.parseInt(st.nextToken());
    dest = Integer.parseInt(st.nextToken());

    graph.get(src).add(dest);
    graph.get(dest).add(src);
}

 

알고리즘

완전탐색 - DFS (백트래킹)

• 모든 가능한 친구 관계를 탐색합니다.

 

코드

private static void dfs(int start, int depth) {
    if (depth == 5) {
        isExistFiveInRow = true;
        return;
    }

    visited[start] = true;
    for (int friend : graph.get(start)) {
    	if (isExistFiveInRow) break;
        
        if (visited[friend]) continue;        
        dfs(friend, depth+1);
    }
    visited[start] = false;
}

• 방문처리: 중복 탐색 방지
• 가지치기: 요구하는 친구관계의 유무를 판별하는 것이 목적 -> 발견 시, 탐색 종료

 

Result

time complexity

• O(N^5)

 

performance

• 20,988kb / 296ms

 

3. 개선

자료구조

링크드 리스트

static class Node {
    final int idx;
    final Node friend;

    public Node(int idx, Node friend) {
        this.idx = idx;
        this.friend = friend;
    }
}

nodes = new Node[N];

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

    nodes[src] = new Node(dest, nodes[src]);
    nodes[dest] = new Node(src, nodes[dest]);
}

 

알고리즘

private static void dfs(int start, int depth) {
    if (depth == 5) {
        isExistFiveInRow = true;
        return;
    }

    visited[start] = true;
    for (Node tmp = nodes[start]; tmp != null; tmp = tmp.friend) {
        if (isExistFiveInRow) break;

        int friendIdx = friend.idx;
        if (visited[friendIdx]) continue;
        dfs(friendIdx, depth+1);
    }
    visited[start] = false;
}

 

Result

performance

• 15,024kb / 212ms