[Programmers] 네트워크(Python) / DFS / BFS

프로그래머스 고득점 KIT > 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > Level 3 네트워크 문제이다.

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

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

그래프 기본 문제로, BFS와 DFS 알고리즘으로 각각 코딩해보았다.

시간, 메모리는 비슷하게 나왔다.

 

다음은 BFS로 풀이한 파이썬 코드이다.

from collections import deque

def solution(n, computers):
    answer = 0
    visited = [0] * n
    for i in range(n):
        if visited[i]:
            continue
        visited[i] = 1
        Q = deque([i])
        while Q:
            x = Q.popleft()
            for j in range(n):
                if computers[x][j] and not visited[j]:
                    visited[j] = 1
                    Q.append(j)
        answer += 1
    return answer

 

아래는 DFS로 접근한 파이썬 코드이다.

def dfs(start, computers, visited, n):
    for i in range(n):
        if computers[start][i] and not visited[i]:
            visited[i] = 1
            dfs(i, computers, visited, n)

def solution(n, computers):
    answer = 0
    visited = [0] * n
    for i in range(n):
        if visited[i]:
            continue
        visited[i] = 1
        dfs(i, computers, visited, n)
        answer += 1
    return answer

 

* 고찰 : 기본적인 문제일수록 실수 없이 빠르게 풀어내자!