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

문제 설명

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

풀이 과정

Wrong Access

2시간 미만의 시간을 잡고 풀었지만 시간이 2배 이상 걸렸다.
시간조절 패인은 무엇이었을까?

• 1부터 4까지의 노트 중 거쳐간 노드의 경로가 [ 1, 1-3, 1-2, 1-2-3, 1-2-3-4 ] 이런식일때 모든 노트를 포함하는 경로가 있으므로 네트워크는 1이다.

이런 경우를 고려하지 못했기때문에 시간이 오래걸린것 같다

lv 3이상의 그래프 문제일 경우 30분 이상은 투자해서 설계를 꼼꼼하게 한 후 구현을 시작하는게 제일 빨리 푸는 방법인것같다.

설계시간 아끼려고 문제 대충보고 바로 구현하기 시작했다가는 오늘처럼 시간을 땅에 버리기 쉽상이니 주의하자!!

Correct Access

• computers의 노드 전체를 돌면서 dfs(node)를 돌린다.

  • dfs를 돌면서 node에서 시작한 경로를 저장하고 string으로 바꿔서 route_list에 넣는다
    • 여기서 route_list는 set()이다!! (중요)

• node를 다 돌았다면 route_list의 length를 return 한다.

코드

route_list = set()

def solution(n, computers):

    for i in range(n):
        computers[i][i] = 0

    for node in range(n):
        print(node,'번째 노드')
        route_list.add(dfs(node, computers, stack=[]))
        
    answer = len(route_list)
    return answer

def dfs(start, computers, stack):
    visited = [False] * len(computers)
    visited_node = []
    stack.append(start)

    while stack:
        now = stack.pop()

        # 이전에 방문경험없다면
        if not visited[now]:
            visited[now] = True
            visited_node.append(now)

            # 자식노드가 있다면
            for child in range(len(computers[now])):
                if computers[now][child]:
                    stack.append(child)

    str_visited = ''.join(map(str, sorted(visited_node)))
    return str_visited