[코테리뷰] DFS/BFS - Lv3. 네트워크

 

https://programmers.co.kr/learn/courses/30/lessons/43162

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

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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

예시

아래와 같이 2개의 네트워크가 있습니다.

접근방법(BFS)

- BFS 란? 

  - 너비 우선탐색 : 가까운 노드부터 탐색하는 알고리즘

  - 보통, 선입선출인 큐 자료구조를 이용

 

- 동작방식?

  1) 탐색 시작 노드를 큐에 삽입하고, 방문처리를 한다.

  	bfs.append(visited.index(0)) # 시작노드 (방문하지 않은 노드를 찾아서) 큐 삽입
        while bfs: 
            node=bfs.pop(0) # 시작노드 꺼내기
            visited[node]=1 # 방문처리  
       

  2) 큐에서 노드를 꺼내, (1)인접 노드 중에서 (2)방문하지 않은 노드를 모두 큐에 삽입하고, 방문처리를 한다. 

          for i in range(n): # 자료 탐색
                if visited[i]==0 and computers[node][i]==1: # 큐 삽입 조건 : (1),(2)
                    bfs.append(i) # 큐 삽입

 

  3) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 

 

- 필요한 자료구조?

  - 큐 (본 문제에서는 리스트를 사용)

  - 방문여부 리스트

def solution(n, computers):

    answer=0 # 정답 변수
    bfs=[] # 스택 준비
    visited=[0]*n # 방문여부 리스트

    while 0 in visited: # 방문이 다 되어질 때까지!(visited에 0 이 없을 때까지)
        bfs.append(visited.index(0)) # 방문하지 않은 노드 인덱스를 찾아서 추가
        
        while bfs: # bfs 리스트에 노드가 있을 때
            node=bfs.pop(0) # 앞에서부터 node pop!
            visited[node]=1 # 방문처리해주기

            for i in range(n): # 인접 노드를 방문하기
                if visited[i]==0 and computers[node][i]==1: # 아직 방문하지 않았고, 서로 연결되어 있을 때
                    bfs.append(i) # 연결된 i를 추가해주기

        # 연결되어 있는 노드의 방문이 끝났다면,
        answer+=1 # 카운트해주기
    return answer

# 정답 확인
print(solution(n=3,computers=[[1, 1, 0], [1, 1, 0], [0, 0, 1]]))

참고: list 자료형으로도 append와 pop을 통해 queue를 이용할 수 있지만, deque를 쓰면 더 빠르게 이용가능합니다. 

- from collections import deque

- bfs=deque()

- deque.popleft()