[Python/프로그래머스]네트워크_(DFS,유니온파인드)

 

 

 

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

코딩테스트 연습 - 네트워크

 

 

---

 

 

문제 설명 : 

 

 

문제를 보고 computers의 배열 설명이 잘 이해가 가지않았는데 몇번 읽어보고 이해했다.

 

computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]

 

이렇게 computers가 있을 때 

다음 그림과 같이 생각하면 된다.

1행 1열, 2행 2열, 3행 3열은 당연히 1이다.  자기자신과 자기 자신이기 때문이다.

 

그 이외에 2행 1열, 2행 2열이 1인 것을 확인할 수 있다. 

즉 2번과 1번 컴퓨터가 연결된것이다. 

 

 

 

 

푸는 법 : 

 

1. dis 배열을 만들어 컴퓨터의 방문여부를 확인할수있게한다.

 

2. for 문을 이용해 컴퓨터를 돈다.

 

3. 만약 안가본 컴퓨터가 있다면 간다. (dfs 함수 실행)

 

4.  dfs함수는 가봤음을 알리고 이와 연결된 컴퓨터중 안가본 컴퓨터가 있으면 간다. 

 

 

 

 

---

 

 

코드 : 

def solution(n, computers):
    answer = 0
    vis = [0 for i in range(n)] 
    def dfs(now) :
        vis[now] = 1 # 가봤음을 알린다
        for new in range(n) : 
            if computers[now][new] and vis[new]==0 : # 다른 컴퓨터와 연결되어있고 안가봤다면 
                dfs(new)
                
    for i in range(n) : # 컴퓨터를 돌면서
        if vis[i] == 0 : # 안가봤다면
            dfs(i) # 가본다 # 연결된 컴퓨터를 1으로 만든다.
            answer+=1  # 한개 네트워크 추가 
            
    return answer

 

 

 

DFS를 밖으로 뺀 코드 : 

def dfs(idx,computers,n,vis) :
	# 이제 가봄
    vis[idx] = 1 
    # 나랑 연결된 모든 것들 중 안가본 곳을 찾는다
    for j in range(n) :
        if vis[j] == 0 and computers[idx][j]==  1 : 
            dfs(j,computers,n,vis)

def solution(n, computers):
    cnt = 0
    vis = [0]*n
    for i in range(n) :
    	# 안가봤어?
        if vis[i] == 0 :
            dfs(i,computers,n,vis)
            cnt+=1 
    return cnt

 

 

---

 

유니온 파인드 이용 코드 : 

def union(parent,a,b) :
    a = find(parent,a)
    b = find(parent,b)
    if a< b : parent[b] = a 
    elif a >b : parent[a] = b 

def find(parent,x) :
    if x != parent[x] : parent[x] = find(parent,parent[x])
    return parent[x]

def solution(n, computers):
    parent = [0]*(n+1)

    
    for i in range(1,n+1) :
        parent[i] = i
    
    for i in range(n) :
        for j in range(n) :
            if computers[i][j] and i!=j : union(parent,i+1,j+1)
        
    maps = {}
    for idx in range(1,len(parent)) :
        v = find(parent, idx)
        if not v in maps: maps[v] = 1
        
    return len(maps)

 

 

기본 유니온파인드랑 동일하다. 

집합의 개수를 셀 때 딕셔너리 자료구조를 이용해서 

루트 노드가 딕셔너리에 없으면 추가하고 

마지막에는 딕셔너리의 길이를 반환한다.

 

 

 

 

 

참고 블로그 : 

 

https://velog.io/@op032/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC-python

프로그래머스 네트워크 (python)

https://reliablecho-programming.tistory.com/116?category=971588 

[프로그래머스] LEVEL3 네트워크 (유니온파인드 풀이) - 파이썬

 

 

복습 : 

 

✅ 20220620

✅ 20220623

✅ 20220624

✅ 20220625

✅ 20220626

✅ 20220628

✅ 20220630

🐾 20220922

🐾 20220924