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

네트워크

문제 링크

나의 풀이

잘못된 풀이

def solution(n, computers):
    answer = 0
    cnt = []
    for i in range(len(computers)):
        list1 = []
        for j in computers:
            list1.append(j[i])
        if 0 not in list1:
            cnt.append(1)
        else:
            cnt.append((list1.count(0)+(list1.count(1)-1)))

    return min(cnt)

• DFS 또는 BFS 개념을 적용하지 않고 요령껏 풀어보려고 했으나 실패하였다. 테스트 케이스 2개 정도는 통과하였으나 나머지 케이스는 전부 정확도 테스트에서 바로 막혔다. 공부한 DFS를 적용해서 풀어봐야겠다.

2차 풀이

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

    for node in range(n):
        if visited[node] == False:
            dfs(n, computers, node, visited)
            answer += 1

    return answer

def dfs(n, computers, node, visited):
    visited[node] = True #방문한 노드는 True

    for i in range (n):
        if i != node and computers[node][i] == 1:
            if visited[i] == False:
                dfs(n, computers, i, visited)
    return visited

• DFS 개념을 활용하여 문제를 풀었다. 일단 처음에 방문하지 않은 노드는 False로 하는 리스트를 생성한다.
• 방문한 노드는 True가 되며, 주어진 n에 따라 DFS로 최대한 노드들을 방문하고 빠져나오면 그것이 하나의 네트워크가 된다.
• DFS는 물론이고 재귀를 적용하는 것이 아직 너무 미숙하다... 연습이 필요하다 ... BFS 개념공부 후 BFS로도 풀어봐야겠다.