핵심 친구 찾기 문제

이번에 풀어본 문제는 삼성 소프트웨어 역량테스트라는 책에 있는 모의고사 문제인 핵심 친구 찾기문제입니다!!

먼저 문제에 대한 설명은 이러합니다. 담임 선생님이 새 학기가 되서 학생들 친구관계를 조사하고 있어요. 여기서 선생님은 핵심 친구를 찾으려고 하는데,

핵심 친구란 해당 친구가 빠지게 되면 친구관계에서 연결 되지 않는 친구가 생기는 경우 그 친구를 핵심 친구라고 해요.

예를 봅시다.

이런 친구관계 그래프가 있다고 합시다. 여기서 만약 3번 친구가 없다고 생각하고 다시 친구 관계도를 봅시다.

오호 3번 친구가 없어도 나머지 친구들이 잘 이어져 있네요. 이런 경우 3번 친구는 핵심 친구가 아니게 되는거죠.

이번엔 6번 친구가 빠졌다고 생각해봅시다.

오호 6번 친구가 빠지니까 7,8,9 친구가 다른 애들이랑 연결이 안 되네요!! 이런 경우 6번 친구가 핵심 친구가 되는거에요. 이해 되셨나요??

---

보통 이런 그래프 문제가 나오면 BFS, DFS를 사용해서 문제를 풀게 됩니다(대부분...).

BFS & DFS DFS(Depth First Search)

BFS & DFSBFS(Breadth First Search)

제가 선택한 풀이법은 BFS를 사용해서 풀었어요. 사실 두 개는 queue를 쓰냐 stack을 쓰냐 차이니까 상관 없을 듯ㅎㅎ 먼저 코드를 봅시다.

void FriendSearch(int noPass)
{
    //noPass는 친구 번호로 이 친구를 지나지 않고 BFS를 지났는데
    //모두 visit가 되면 noPass는 핵심 친구가 아니라는 것.
    queue<int> que;
    bool visit[15] = {false,};
    // 맵을 탐색할 때 noPass=1이면, BFS의 시작을 2번 부터.
    if(noPass==1) que.push(2);
    else          que.push(1);

    while(!que.empty())
    {
        int target = que.front(); // 방문 친구를 찾자
        que.pop();
        visit[target] = true; // 방문했으니까 ture때려
        for(int i=1; i<=students; i++)
        {
            //그 다음 연결된 친구가 noPass이고 방문 안한 상태라면 push
            if((map[target][i]==1)&&(i!=noPass)&&(visit[i]==false)) que.push(i);
        }
    }
    if(!VisitCheck(noPass,visit)) //noPass를 제외하고 나머지 중 방문 안된 애가 있으면 noPass는 핵심친구가 되는거임.
    {
        Pilsu[PilsuAmount] = noPass;
        PilsuAmount++;
    }
}

먼저 visit을 사용해서 풀었어요. BFS를 따라서 계속 vertex를 탐색합니다. noPass는 방문 안 할 친구가 되는데, 저는 1번부터 마지막 친구까지 이어져있나 확인하게 했기 때문에 시작 노드를 처음 설정해주고, 탐색 진행!! 별로 어렵지 않죠??ㅎㅎ 

전체 코드는 여기있습니다! https://github.com/dinoHee/FindFriends