[BOJ]4195번: 친구 네트워크

 

문제: https://www.acmicpc.net/problem/4195

---

단순 DFS로 탐색하면 시간초과로 터지는 문제입니다.

Union & Find를 통해 해결했습니다.

 

풀이는 jason님 (https://jason9319.tistory.com/41) 링크를 참고했는데요.

 

일반 Union & Find 보다 한 단계 더 나아가 자식의 숫자를 저장하고 있어야 합니다.

 

그러므로 문제가 생기는 부분이 있습니다.

 

바로 friend1, friend2 로 들어오는 관계가 이미 부모 - 자식 관계인 경우 입니다.

 

BEFORE의 경우 무조건 부모쪽에 더하도록 만들어주었고,

AFTER는 부모 - 자식 관계인 경우 부모를 리턴, 부모 - 자식 관계가 아닌 경우 더하도록 만들었습니다.

 

BEFORE 코드가 문제가 되는 이유는

이미 부모 - 자식인 경우에는 부모의 갯수만 리턴하면 되는데 또 부모 += 자식이 되어버려 틀린 답이 됩니다.

 

BEFORE

int cntMember(string f1, string f2)
{
    if (child.find(f1) == child.end()) 
    {
        child[f1] = 1;
    }
    if (child.find(f2) == child.end())
    {
        child[f2] = 1;
    }

    child[f1] += child[f2];
    return child[f1];
}

---

AFTER

int cntMember(string f1, string f2)
{
    if (child.find(f1) == child.end()) 
    {
        child[f1] = 1;
    }
    if (child.find(f2) == child.end())
    {
        child[f2] = 1;
    }

    if (f1.compare(f2) == 0)
        return child[f1];
    else 
    {
        child[f1] += child[f2];
        return child[f1];
    }
}

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ4195.cc