반응형
문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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 |
본 문제는 너비우선 탐색(BFS) 문제입니다. 연결된 간선을 기준으로 네트워크 여부를 판별하면 되기 때문에 Depth 의 개념은 필요하지 않습니다. 즉, 주어진 그래프 상에서 연결되어있는 노드를 차례로 방문하면 됩니다.
파이썬으로 BFS를 구현하는 방법은 선입선출(FIFO) 구조인 큐(Queue)를 이용하는 방법이 주로 사용됩니다. Queue를 사용하는 방법은 파이썬에서 deque 또는 list를 이용해 간단히 구현할 수 있습니다. 차이점이라면, deque는 push/pop 등 연산이 빈번한 알고리즘에서 리스트보다 더욱 빠른 연산속도를 가지고 있습다. 따라서, 최적화(효율성) 옵션이 있는 코딩문제의 경우 deque를 활용해 연산최적화를 할 수 도 있습니다.
BFS를 구현하는 방법은 아래와 같습니다.
| 1. 방문 여부를 확인 할 visited list 와 방문 시작 노드를 선언한다. 2. 다음에 방문할 노드를 queue에 저장한다. 3. 더 이상 방문할 노드가 없을 때 까지(visited list가 다 채워졌을 때 까지) 탐색을 반복한다. 4. queue에 맨 앞의 노드를 꺼낸다. 5. 해당 노드가 아직 방문하지 않았다면, 방문 리스트에 추가해주고 다음 노드들을 queue에 추가해준다. |
위 내용을 코드로 구현한 정답은 아래에 있습니다.
더보기
def solution(n, computers):
answer = 0
visited = [0]*n # 1. 방문리스트 선언
while sum(visited) != n: # 3. 모두 방문할 때 까지
bfs = [visited.index(0)] # 2. 방문할 노드를 선택
answer += 1
while bfs:
node = bfs.pop(0) # 4. 왼쪽부터 하나씩 뺴면서 노드검사
for i, line in enumerate(computers[node]):
if line and not visited[i]: # 5. 노드가 비어있지 않고 방문하지 않았다면,
visited[i] = 1
bfs.append(i)
return answer반응형