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

프로그래머스 코딩테스트 고득점 Kit - 깊이/너비 우선 탐색(DFS/BFS)

• Lv 3. 네트워크 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/43163

Code

from collections import deque

def solution(n, computers):
    answer = 0

    check = [False for _ in range(n)]

    ans = []
    network = []

    q = deque()

    for c in range(n):
        if(check[c] == False):      # 확인하지 않은 컴퓨터 번호라면 큐에 삽입
            q.append(c)

            while(q):
                curr_comp = q.popleft()
                for i in range(n):      # 현재 행의 모든 열을 살펴보면서
                    if(computers[curr_comp][i] == 1 and check[i] == False):     # 만약 연결이 되어있고, 이전에 확인한 기록이 없다면
                        check[i] = True     # 확인했다고 표시
                        network.append(i)   # 하나의 네트워크로 판단하여 network 배열에 삽입
                        q.append(i)         # 연결되어 있는 열에서 또 연결된게 있는지 다음 탐색을 위해 큐에 삽입
        if(network):    # 형성된 네트워크가 있다면 -> ans 배열에 삽입
            ans.append(network)
            network = []

    print(ans)
    answer = len(ans)   # 네트워크의 총 개수는 ans 배열에 들어있는 네트워크들의 개수

    return answer

if __name__ == '__main__':
    print(solution(3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]))       # 2
    print(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))       # 1

풀이 및 해설

• BFS로 해결
  • 계속 연결되어 있는지 타고타고 들어가서 확인해야하므로 현재 컴퓨터에서 연결되어 있는 컴퓨터 번호는 다음 행에서의 확인을 위해 큐에 삽입하기
  • 방문하지 않은 컴퓨터라면 우선 큐에 삽입 → 큐를 순회하면서 현재 컴퓨터 번호(행)의 모든 열을 살펴봄
  • 만약 연결이 되어 있고 (값이 1이고), 해당 컴퓨터 번호(열)을 이전에 방문한 기록이 없다면 → 큐에 삽입, 방문했다고 표시, 하나의 네트워크로 판단하여 network 배열에 삽입
• network 배열이 비어있지 않으면 → ans 배열에 삽입
  • 네트워크의 총 개수는 ans 배열에 들어있는 네트워크들의 개수

What I learned

• DFS 로 푸는 방법

def solution(n, computers):
    answer = 0
    visited = []

    def newRoot (i,n,visited):
        for j in range(n):
            if computers[i][j] == 1 and j not in visited:
                visited.append(j)
                newRoot(j,n,visited)

    for i in range(n):
        if i not in visited :
            visited.append(i)
            answer = answer+1
            newRoot(i,n,visited)

    return answer