프로그래머스 LV3 - 네트워크

문제 링크

풀이 1

def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]
    for com in range(n):
        if visited[com] == False:
            DFS(n, computers, com, visited)
            answer += 1 #DFS로 최대한 컴퓨터들을 방문하고 빠져나오게 되면 그것이 하나의 네트워크.
    return answer

def DFS(n, computers, com, visited):
    visited[com] = True
    for connect in range(n):
        if connect != com and computers[com][connect] == 1: #연결된 컴퓨터
            if visited[connect] == False:
                DFS(n, computers, connect, visited)

풀이 해석

• 컴퓨터를 처음부터 방문하며 방문하지않았을 경우 dfs 함수를 통해 최대한 방문하고 나온다
• dfs 함수에서 최대한 방문하기 위해 재귀함수를 통해 끝까지 방문하고 나온다
• 다 방문하고 나오면 answer += 1을 통해 네트워크 수를 증가시킨다

풀이 2

def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]
    for com in range(n):
        if visited[com] == False:
            BFS(n, computers, com, visited)
            answer += 1
    return answer

def BFS(n, computers, com, visited):
    visited[com] = True
    queue = []
    queue.append(com)
    while len(queue) != 0:
        com = queue.pop(0)
        visited[com] = True
        for connect in range(n):
            if connect != com and computers[com][connect] == 1:
                if visited[connect] == False:
                    queue.append(connect)

풀이 해석

• BFS를 통한 풀이로 queue에 append pop을 하며 queue가 빌 때까지 탐색을 진행한다
• 탐색이 종료되면 네트워크를 하나 추가한다