728x90
반응형
문제 설명:
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
문제 풀이:
위와 같이 경로를 탐색해야 하는 경우 깊이/너비 우선 탐색으로 풀어야 하는 경우가 많고, 이 문제 역시 깊이 우선 탐색(DFS)로 풀어야 하는 문제였다. 깊이 우선 탐색은 stack을 이용하고, 너비 우선 탐색은 queue를 사용하는데, python의 list는 stack가 비슷하게 작동을 하기 때문에 stack이라는 리스트를 만들었고, 이미 지나왔던 경로임을 표시하기 위해서 visited라는 bool list를 만들었다.
A 컴퓨터에서 시작해서 지나가는 컴퓨터들을 전부 True로 바꾸면서 이동을 하였고, 더 이상 움직일 수 없을 때까지 반복을 하도록 하였다. 그리고 또한 이 과정을 하나의 count로 취급해 하나의 network가 생겼다고 생각을 하였다. 따라서 모든 컴퓨터가 True가 될 때까지 이 count를 반복해서 하면 network의 수를 구할 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | def Network(computers,visited,SNode): stack=[SNode] while stack: path = stack.pop() if not visited[path]: visited[path]=True for i in range(len(computers)): if computers[path][i]==1 and not visited[i]: stack.append(i) def solution(n,computers): answer=0 visited=[False for i in range(n)] idx=0 while not all(visited): if not visited[idx]: Network(computers,visited,idx) answer+=1 idx+=1 return answer | cs |
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1011. Fly me to the Alpha Centauri (0) | 2019.07.05 |
|---|---|
| [Programmers]Lv 3. 여행경로 (0) | 2019.07.04 |
| [BOJ]11057. 오르막 수 (0) | 2019.07.01 |
| [BOJ]1436. 영화감독 숌 (0) | 2019.06.29 |
| [BOJ]1018. 체스판 다시 칠하기 (0) | 2019.06.28 |