네트워크

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

여기까지 왔으면 문제는 알고 있겠지 모르면 보고 오도록

컴퓨터 네크워크 몇 그룹이 있는지 찾는 문제다
노드로 이어져있으니까 연결 연결해서 몇 개가 나오는지 본다

일단 이런 걸 저번에 한번 본 적이 있는데 유니언 파인드를 사용해 풀었다 이것도 똑같은 문제니까 유니언 파인드를 사용한다 말 그대로 찾고 합치고 반복한다

이 방법이 유니언 파인드가 맞는지는 모르겠지만 뭐 비슷한 느낌인 듯
만약 i, j 가 주어졌을 때 딕셔너리에 해당 값이 없으면 둘 중 한 개의 노드가 상대방을 향하게 만든다
elif 둘 중에 한 개에만 값이 있는 상태고 한 개는 없으면 값이 없는 노드의 방향을 값이 있는 쪽으로 향하게 만든다
else 마지막으로 2개의 값 모두 방향이 있으면 각자 본인에게 향하는 노드의 수가 적은 쪽의 노드 모두를 상대방 방향으로 향하게 한다 이런 식으로 하면 한 집단의 방향은 결국 1개의 값을 가리키게 된다

이런 집단의 수가 네트워크의 수

 

네트워크로 묶여있어서 같은 노드중 한곳의 ip 가 차단 당하면 모두 차단당한다..

 

def solution( n,t):
    d={}
    d1={}
    for i in range(len(t)):
        for j in range(len(t[i])):
            if t[i][j]==1:
                d.setdefault(i,-1)
                d.setdefault(j,-1)
                if d[i]==d[j]!=-1:
                    continue
                if i==j and d[i]==d[j]==-1:
                    d[i]=i
                    d1[i]=set([i])
                    continue
                if -1== d[i] and -1== d[j]:
                    d[i]=i
                    d[j]=i
                    d1[i]=set([i,j])
                elif -1== d[i]:
                    d[i]=d[j]
                    d1[d[j]].add(i)
                elif -1== d[j]:
                    d[j]=d[i]
                    d1[d[i]].add(j)
                else:
                    if len(d1[d[i]])<len(d1[d[j]]):
                        c=d[i]
                        for k in d1[c]:
                            d[k]=d[j]
                            d1[d[j]].add(k)
                        del d1[c]
                    else:
                        c=d[j]
                        for k in d1[c]:
                            d[k]=d[i]
                            d1[d[i]].add(k)
                        del d1[c]
    return len(d1)