[python] 프로그래머스 > DFS/BFS > 네트워크

<문제>

- 문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

- 제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

- 입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

 

- 입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

 

<나의 풀이>

못풀었다.....

 

<다른사람의 풀이>

def solution(n, computers):
    answer = 0
    cnt = 0
    visited = [0]*n
    def dfs(c):
        visited[c] = 1
        for s in range(n):
            if visited[s] is not 1 and computers[c][s] is 1:
                dfs(s)
    for i in computers:
        if visited[cnt] is not 1:
            dfs(cnt)
            answer+=1
        cnt+=1
    return answer

 

def solution(n, computers):
    answer = 0
	# 연결여부 체크 (0 :미확인, 1:확인)
    check = [0] *n
    
    def connect(node):
		# 확인으로 미리 체크
        check[node] = 1
		# 다른 컴퓨터와 연결되어있는지 검사
        for x in range(n):
			# 아직 check가 미확인 상태이고 실제로 연결고리가 있다면
            if check[x] == 0 and computers[node][x] :
				# x 컴퓨터와 다른 연결된게 있는지 확인
                connect(x)
			# 체크확인 된 상태이거나 연결고리가 없을때는 for문 계속진행
 	
	
	# 모든 컴퓨터가 연결확인한 상태일때까지 반복
    while 0 in check:
		# 연결 미확인 컴퓨터에서 제일 숫자 작은 컴퓨터 인덱스 고르기
        index = check.index(0)
		# 해당 컴퓨터와 연결된게 있는지 확인
        connect(index)
		# connect 가 끝났다.. ==> 연결된 컴퓨터 다 찾아서 check 1로 만들었다
		# 답 1증가 
        answer += 1
        
    return answer

 

def solution(n, com):
    answer=0
    check=[0]*n
    st=[]
    for i in range(len(com)):
    ### check[i] : 시작할 땐 첫 네트워크이므로 answer +=1. 이후 연결된 부분들은 두번째 for문에서 dfs로  모두 순회하기 때문에,
    ### check가 1이 되어있다. -> 아직도 0인 곳은, 아직 순회하지 않은(연결되지 않은 네트워크)
        if check[i]==0:
            answer+=1
        for j in range(len(com[i])):
     ### i==j인 경우는 자기자신을 의미하므로 넘어감. [i][j]==1인 경우는 연결된 경우 -> stack에 넣어서 dfs.
           if i!=j and com[i][j]==1:
               st.append(j)
        while len(st)!=0:
            top=st.pop()
            check[top]=1
            for k in range(len(com[i])):
                if com[top][k]==1 and check[k]==0:
                    st.append(k)
    return answer