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

문제

문제

 

처음 작성한 코드

def solution(n, computers):
    answer = 0
    visited = []
    stack = [0]
    all_stack = set([i for i in range(n)])
    while True:
        if len(visited)==n:
            return answer+1
        if len(stack)==0:
            answer+=1
            stack.append(list(all_stack-set(visited))[0])
        a = stack.pop()
        if a not in visited:
            visited.append(a)
        for j in range(n):
            if computers[a][j]==1 and a!=j and j not in visited:
                stack.append(j)

1. 탈출조건: 모든 노드를 다 방문했을 때
2. len(stack)이면 네트워크가 끊긴거라 answer+=1 하고 visited 안한 노드를 stack에 넣고 그 노드가 속해있는 네트워크를 다시 돈다.
3. stack(방문해야할 노드)에서 pop()하여 방문안했으면 방문을 하고, 노드의 이웃노드들을 stack에 넣는다. (왜냐면 방문해야하니까~)

깨달은 점

• 문제를 통과하긴 했는데 DFS인지 BFS인지 모르겠다..
• 네트워크가 끊기면 다음 방문할 노드를 어떻게 정할까 고민했었는데 set을 이용해서 all_stack에서 지금까지 방문한 노드의 리스트를 빼고 그 중 가장 앞에 있는 노드로 정했다. list는 빼기가 안되는데 set은 된다. set은 인덱스로 접근이 안되서 다시 list()로 변환하고 인덱스 접근을 시도해야한다.
• 오늘은 쉽게 푼 것 같다.