[알고리즘] 프로그래머스 네트워크 파이썬 | DFS

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

문제

나의 풀이

def dfs(i, computers, visited):
    visited[i] = True
    for j in range(len(visited)):
        if visited[j]:
            continue
        if computers[i][j] == 0:
            continue
        dfs(j, computers, visited) # <---- 여기

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

처음에 RecursionError 런타임 에러가 출력되었다.
다른 코드와 비교했을 때 같은 알고리즘인데 나만 에러가 나서 한참을 찾았다.
실수로 dfs()에 j가 아닌 i를 넘겨줘서 발생했던 에러였다.

약 2년 전에도 같은 실수를 범했는데 또 ㅎㅎ

다른 풀이

BFS를 사용하는 풀이이다.

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)

얻어가기

i와 j 변수를 사용할 때 자주 실수한다. 앞으로는 피하도록 하자.