[c++] BOJ 13023 :: ABCDE (테스트케이스, 코드)

ABCDE

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	6509	1863	1222	28.399%

문제

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

테스트케이스

5 7
2 1
2 4
3 4
1 3
7 1
2 7
2 3
=> 1 (24317)
=> 1 (13427)

6 8
1 7
7 6
1 2
6 2
6 5
4 5
1 5
4 7
=> 1 (17654)

6 7
1 7
1 2
6 2
6 5
4 5
1 5
4 7
=> 1 (17456)

5 5
0 1
1 3
1 2
2 3
3 4
=> 1 (01234)

나의 답

알고리즘

1. 친구 관계를 저장한다.
2. brute force로 친구관계를 하나씩 살피면서 5명이 연달아 나올 수 있는지 test한다.

• 2번 과정에서 친구관계는 (a,b) (b,a) 를 따로 다 계산해야함

• 2번에서 친구를 찾는 과정의 복잡도를 최대한 줄여야함

  단순하게 생각해서 arr로 처리하면 메모리도 많이 잡아먹고 찾기도 힘들다. 2000번을 다 살펴보아야하기 때문.

• 따라서 본인은 map으로 구현하여 해당 사람의 친구만 빼오는 식으로 진행하였다.

• 2번에서 5명 중에 같은 사람이 나오지 않도록 처리해야함

  처음 코드에서는 그냥 5명의 사람을 담는 arr에 있는지 없는지를 즉시 check하는 코드로 구현하였는데, 주의할 점은 초기화를 -1로 해두는 것이다.

  => 초기화를 하지 않으면 0으로 초기화되기 때문에 0번째 사람이 있는 것처럼 처리된다.

• 따로 visited했는지 check하는 arr를 두고 해도 정답처리 된다.

코드

<첫번째 코드>

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
int N, M;
map<int, vector<int>> friends;
map<int, vector<int>>::iterator iter;
int arr[5];

bool isInArr(int num) {
    for (int i = 0; i < 5; i++) { // 5
        if (arr[i] == num)
            return true;
    }
    return false;
}

int fiveFriends(int* in, int size) {
    if (size == 5) {
        return 1;
    }

    int last_person = in[size-1];
    auto tmp_v = friends[last_person];
    int v_size = tmp_v.size();
    for (int i = 0; i < v_size; i++) { // 2*10^3
        if (!isInArr(tmp_v[i])) {// arr에 없으면
            in[size] = tmp_v[i];
            if (fiveFriends(in, size + 1) == 1) // 깊이 5 => 최대 3번 => 2*10^9
                return 1;
            in[size] = -1;
        }
        else
            continue;
    }
    return 0;
}

int main() {
    cin >> N >> M;
    while(M--){
        int a, b;
        cin >> a >> b;
        friends[a].push_back(b); friends[b].push_back(a);
    }

    int flag = 0;

    for (iter = friends.begin(); iter != friends.end(); iter++) { // 2*2*10^3
        auto tmp = *iter;
        arr[0] = tmp.first;

        auto tmp_v = tmp.second;
        int v_size = tmp_v.size();
        for (int i = 0; i < v_size; i++) {
            arr[1] = tmp_v[i];
            if (fiveFriends(arr, 2) == 1) {
                flag = 1;
                break;
            }
            arr[1] = -1;
        }
        if (flag)
            break;
        arr[0] = -1;
    }

    cout << flag;
}

<두번째 코드>

바뀐 점은 //* 로 표시해두었다.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
int N, M;
map<int, vector<int>> friends;
map<int, vector<int>>::iterator iter;
int visited[2000];
int arr[5];

/*
bool isInArr(int num) {
    for (int i = 0; i < 5; i++) { // 5
        if (arr[i] == num)
            return true;
    }
    return false;
}
*/

int fiveFriends(int* in, int size) {
    if (size == 5) {
        return 1;
    }

    int last_person = in[size-1];
    auto tmp_v = friends[last_person];
    int v_size = tmp_v.size();
    for (int i = 0; i < v_size; i++) { // 2*10^3
        if (visited[tmp_v[i]]==0) {// arr에 없으면 //*
            in[size] = tmp_v[i];
            visited[tmp_v[i]] = 1; //*
            if (fiveFriends(in, size + 1) == 1) // 깊이 5 => 최대 3번 => 2*10^9
                return 1;
            visited[tmp_v[i]] = 0; //*
        }
        else
            continue;
    }
    return 0;
}

int main() {
    cin >> N >> M;
    while(M--){
        int a, b;
        cin >> a >> b;
        friends[a].push_back(b); friends[b].push_back(a);
    }

    int flag = 0;

    for (iter = friends.begin(); iter != friends.end(); iter++) { // 2*2*10^3
        auto tmp = *iter;
        arr[0] = tmp.first;
        visited[tmp.first] = 1; //*

        auto tmp_v = tmp.second;
        int v_size = tmp_v.size();
        for (int i = 0; i < v_size; i++) {
            arr[1] = tmp_v[i];
            visited[tmp_v[i]] = 1; //*
            if (fiveFriends(arr, 2) == 1) {
                flag = 1;
                break;
            }
            visited[tmp_v[i]] = 0; //*
        }
        if (flag)
            break;
        visited[tmp.first] = 0; //*
    }

    cout << flag;
}

 

+

• vector의 최대 크기는 32bit 컴퓨터 기준으로 10^9개

• return 형식이 void가 아니면 무조건 return해주어야함

  => 아니면 런타임 에러

• 초기화 잘 해주기