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

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

프로그래머스의 DFS/BFS 레벨3 문제다.

네트워크 노드의 개수와 각 노드가 연결된 노드의 정보가 주어지면 총 네트워크의 개수가 몇 개 인지 확인해야 한다.

 

나는 우선 위 그림 처럼 가상의 Root를 주고 시작했다.

Root로부터 깊이 우선 탐색을 수행한다.

접근하는 모든 노드의 인덱스를 키로 딕셔너리에 저장하고 현재의 탐색의 시작 노드 번호를 값으로 추가한다.

 

첫번째 경우에서는 1번 노드에 접근하고 자기 자신을 제외한 연결된 모든 노드를 탐색한다.

1번 노드에서 2번노드를 거친 후 다시 1번 노드에서 3번 노드로 접근한다.

첫번째 탐색에서 1, 2, 3번 노드를 거쳤으므로 딕셔너리의 1의 값에 1을 저장한다.

 

두번째 경우에서는 1번 노드에 접근하고 2번 노드까지 간 이후 추가 노드가 없으므로 딕셔너리의 1에 1을 저장하고 Root로 복귀한다.

이후 3은 분리된 네트워크의 첫번째 노드이므로 딕셔너리의 3에 값을 3을 저장한다.

 

case1 = { 1 : 1, 2 : 1, 3 : 1 }
case2 = { 1 : 1, 2 : 1, 3 : 3 }

탐색의 결과는 위와 같이 나온다.

이후 딕셔너리의 값을 기준으로 중복을 제거하고 그 값의 개수를 반환하여 해결하였다.

 

 

GitHub - Floodnut/Algorithm: 알고리즘 풀이 모음