python 코딩테스트 - 프로그래머스 네트워크

출처 : 프로그래머스

처음 든 생각

- 하나를 시작해서 끝까지 어디까지 연결되어있는지 파악해야하므로 이건 DFS를 해야한다.

- DFS를 하는 방식을 다시 곱씹어보자.

- 연결되어있는 노드들이 제시된 리스트가 있고, visited 여부를 확인하는 리스트가 또 있어야한다. 그리고 dfs 함수를 선언한 뒤 노드에 연결된 모든 노드들에 대해 반복문을 돌고 조건에 따라 재귀를 구성한다.

 

나의 답

answer = 0
def solution(n, computers):
    global answer
    a=[]
    v = [0] * len(computers)
    def dfs(c):
        global answer
        if v[c] == 1:
            return
        v[c] = 1
        a.append(c)
        for n in range(len(computers[c])):
            if v[n] == 0 and computers[c][n]==1:
                dfs(n)
    
    for i in range(len(computers)):
        tmp = a[:]
        dfs(i)
        if a != tmp:
            answer += 1
    
    return answer

하나의 네트워크가 완성될 때마다 연결된 원소들을 넣어줄 리스트를 하나 선언해주었다.

그리고 방문 여부를 확인할 리스트도 선언해주었다. 0은 미방문, 1은 방문했다는 뜻

 

그 다음 이제 dfs를 돌게 되는데 만약 시작 노드를 이미 방문했다면 다른 네트워크에 포함되어있을테니 바로 함수를 빠져나온다.

 

방문하지 않은 경우 방문했다고 해주고 해당 원소를 a에 넣어준다.

c에 연결된 노드들을 반복문을 통해서 방문하지 않았다면 다시 dfs를 재귀로 돌아준다.

 

시작 노드들에 대해서 반복문을 돌고 네트워크가 추가되었는지 확인한 후 개수를 세주면 된다.

 

문제의 예시를 살짝만 전개해보면,

0번 노드에 대해 dfs를 돌게 되면 a = [0,1]이 될 것이다.

tmp는 dfs이전의 a이므로 []여서 네트워크가 추가됨을 확인할 수 있다.

 

1번 노드에 대해서 dfs를 돌게 되면 0번 노드를 탐색할 때 이미 방문했기 때문에 a는 변동이 없다.

 

2번 노드에 대해서 dfs를 돌게 되면 a = [0,1,2]가 되어 네트워크가 추가됨을 확인할 수 있다.

 

dfs가 어떤 흐름으로 동작하는지 배우기에 아주 좋은 문제였다.

연결 노드 확인, 방문 여부 확인, 다음 재귀적으로 동작하는 함수 구성 이렇게 3박자를 계속 연습해보면 좋을 것 같다.

 

이 문제에서 조금 어려움을 겪었던 부분은 마지막 네트워크 개수 세는 부분에서 비교를 해주는 부분이었다.

tmp = a
dfs(i)
if a!=tmp:
	answer+=1

dfs이전의 a값을 tmp에 저장해놓고 비교할려고 했더니 계속 tmp와 a가 같은 결과를 나타내었다. 결국 같은 메모리 주소를 참조하고 있는 것이기에 a의 리스트 내의 원소가 바뀌면 tmp도 같이 움직이는 걸 뒤늦게 깨달았다.

 

그래서 얕은 복사, 깊은 복사에 대해 검색을 좀 해보았고 위의 답안과 같이 얕은 복사를 해서 데이터는 같지만 주소값을 다르게 처리하여 비교할 수 있었다. 복사의 방법들에 대해서도 절대 까먹지 말고 잘 기억해두자.