1238. [S/W 문제해결 기본] 10일차 - Contact(D4)

시작점부터, BFS 탐색을 하여 마지막 연락 받는 사람을 찾는다.

#include <stdio.h>
#include <memory.h>
#include <queue>
using namespace std;
 
int contact[101][101];
int visit[101];
int main(void) {
    int T=10;
    setbuf(stdout, NULL);
    //scanf("%d\n", &T);
    for (int test_case = 1; test_case <= T; test_case++)
    {
        memset(contact, 0, sizeof(contact));
        memset(visit, 0, sizeof(visit));
        int l, s;
        scanf("%d%d", &l,&s);
        for (int i = 0; i < l / 2; i++)
        {
            int f, t;
            scanf("%d%d", &f,&t);
            contact[f][t] = 1;
        }
        queue<int> q;
        queue<int> last;
        int max = 0;
        q.push(s);//시작점 푸쉬
        visit[s] = 1;
        while (q.size())
        {
            int temp = q.size();
            while (last.size())
                last.pop();
            for (int i = 0; i < temp; i++)//큐에 있는 모든 숫자를 빼서 연락
            {
                int from = q.front();
                q.pop();
                last.push(from);
                for (int j = 0; j < 101; j++)
                {
                    if (contact[from][j] == 1 && visit[j]==0)//from이 연락 가능하고 j가 아직 연락을 안받았다면
                    {
                        visit[j] = 1;
                        q.push(j);
                    }
                }
            }
        }
        while (last.size())
        {
            int temp = last.front();
            last.pop();
            if (temp > max)
                max = temp;
        }
        printf("#%d %d\n", test_case,max);
    }
    return 0;
}