[211123] 프로그래머스 - 네트워크

일치하기만 할 뿐, 더 나은 답이 아닙니다.

[프로그래머스 - 네트워크]

알고 가기

1-1. 재귀 함수

• 자기 자신을 다시 호출하는 함수

def recursive_function():
	print('재귀 중')
	recursive_function()

recursive_function()

• Python 에서는 최대 재귀 깊이 존재

# maximm recurison depth exceded while calling a Pyhon object

• 메모리의 구조가 stack처럼 동작하여 함수 실행
• 재귀 함수 안에 반드시 종료 조건을 명시해야 함

1-2. 유클리드 호제법

• 두 자연수(A, B)의 최대공약수 산출
• A % B = R
• A와B 의 최대공약수 = B와R 의 최대공약수

단계	A	B
1	192	162
2	162(1단계의 B)	30(1단계의 A % B)
3	30(2단계의 B)	12(2단계의 A % B)
4	12(3단계의 B)	6(3단계의 A % B)

• 더 이상 나머지가 존재하지 않다면, 마지막 단계의 B = 구하고자 한 최대공약수

def gcd(a, b):
	if a % b == 0:	# 더 이상 나머지가 존재하지 않는다면 b가 최대공약수
		return b
	else:
		return gcd(b, a % b)

print(gcd(192, 162)) # 6

1-3. 재귀의 유의 사항

• 잘 활용하면 복잡한 알고리즘을 간결히 작성 가능
• 다른 사람이 이해하기 어려운 형태의 코드가 될 가능성을 유의
• 모든 재귀함수는 반복문을 통해 구현 가능, 상황에 따라 두 방법을 선택해야 함

문제

A와 B 연결, B와 C 연결 => A,B,C는 같은 네트워크

컴퓨터의 갯수 n, 연결 정보 2차원 배열 computers 주어졌을 때, 네트워크의 갯수는?

조건

• 1 ≤ n ≤ 200 (자연수)
• 컴퓨터의 번호는 0부터 n-1
• i 와 j 컴퓨터가 연결되어 있다면 => computers[i][j] = 1
• computers[i][i] 는 항상 1

ex

3대의 컴퓨터

연결 정보 배열 => [[1,1,0],[1,1,0],[0,0,1]]

컴퓨터	0	1	2
0	1	1	0
1	1	1	0
2	0	0	1

나의 풀이

def dfs(computers, idx, connected):
    connected[idx] = True  # 컴퓨터 방문
    print(idx, connected)  # 아래
    for j in range(len(computers)):
        # (컴퓨터 번호가 다를 때) AND
        # (두 컴퓨터가 연결되어 있을 때) AND
        # (연결할 컴퓨터가 방문하지 않은 컴퓨터 일 때)
        if idx != j and computers[idx][j] == 1 and connected[j] == False:
            dfs(computers, j, connected)


def solution(n, computers):
    net = 0
    connected = [False] * n  # 방문 유무를 배열로
    for i in range(n):
        print(i, "번 컴퓨터 시작")
        if not connected[i]:  # 방문하지 않은 컴퓨터 일 때
            dfs(computers, i, connected)  # i 번 컴퓨터와 연결된 컴퓨터를 connected 에 표기
            net += 1
    return net

0 번 컴퓨터 시작
0 [True, False, False]
1 [True, True, False]
1 번 컴퓨터 시작
2 번 컴퓨터 시작
2 [True, True, True]