[프로그래머스 문제풀이] 네트워크

문제 풀이 상 깊이/너비 우선 탐색 유형으로 풀이되는 문제이다.

내가 풀은 방법은 아래와 같다.

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

    def dfs(i):
        nonlocal answer
        visited[i] = 1
        for n, c in enumerate(computers[i]):
            if c == 1:
                if 0 == visited[n]:
                    visited[n] = 1
                    dfs(n)

    for i in range(n):
        if visited[i] == 0:
            dfs(i)
            answer+= 1

    return answer

통상 깊이우선탐색을 사용할 때는 스택을 사용하고,
너비우선탐색을 사용할 때는 큐를 사용하는데

이 부분이 현재는 익숙하지가 않아 재귀문법으로 풀이하였다.

스택과 큐를 이용하여 풀이하는 방법은 아래와 같다.

def solution(n, computers):
    answer = 0
    visited = [0 for i in range(n)]
    def dfs(computers, visited, start):
        stack = [start]
        while stack:
            j = stack.pop()
            if visited[j] == 0:
                visited[j] = 1
            for i in range(0, len(computers)):
                if computers[j][i] == and visited[i] == 0:
                    stack.append(i)

    i = 0
    while 0 in visited:
        if visited[i] == 0:
            dfs(computers, visited, i)
            answer += 1
        i += 1
    return answer

def solution(n, computers):
    def BFS(node, visit):
        que = [node]
        visit[node] = 1
        while que:
            v = que.pop(0)
            for i in range(n):
                if computers[v][i] == 1 and visit[i] == 0:
                    visit[i] = 1
                    que.append(i)
        return visit
    visit  = [0 for i in range(n)]
    answer = 0
    for i in range(n):
        try:
            visit = BFS(visit.index(0), visit)
            answer += 1
        except:
            break;
    return answer

코드를 다시 보면서 스택과 큐를 이용해서 푸는 방법을 체화시켜야 겠다.