프로그래머스 코딩테스트 네트워크

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

프로그래머스

 

DFS로 작성하여 스택이 다 빠지면 1씩 반환하여 그 수를 세도록 만들었다

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

    def serch(computers):
        while stakk:
            visited.append(stakk.pop(-1))
            start = visited[-1]
            for i in range(n):
                if computers[start][i] == 1 and i not in visited and i not in stakk:
                    stakk.append(i)
                    computers[start][i] = 0
                    computers[i][start] = 0
            for i in visited:
                computers[i][i] = 0
        return 1

    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1:
                stakk.append(i)
                answer += serch(computers)

    return answer

이렇게 하면 테스트케이스는 통과하는데 문제는 통과를 못한다

그래서 수정을 했다

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

    def search(computers):
        while stack:
            start = stack.pop()
            visited.add(start)
            for i in range(n):
                if computers[start][i] == 1 and i not in visited:
                    stack.append(i)
                    computers[start][i] = 0
                    computers[i][start] = 0
            computers[start][start] = 0
        return 1

    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1 and i not in visited:
                stack.append(i)
                answer += search(computers)

    return answer

1. stakk을 stack으로 수정한 이유는 변수명을 명확하고 의미있게 하기 위해서입니다. stack은 일반적으로 스택 자료구조를 의미하기 때문에 보다 이해하기 쉽고 일반적인 표현입니다.
2. visited를 set()으로 초기화한 이유는 방문한 노드를 중복해서 방문하지 않도록 하기 위해서입니다. set()은 원소의 중복을 허용하지 않는 자료구조이므로 중복 방문을 방지할 수 있습니다.
3. serch 함수 내부에서 visited를 set()으로 변경한 이유는 방문한 노드를 빠르게 확인하기 위해서입니다. set()은 원소의 포함 여부를 빠르게 확인할 수 있으므로 visited에서의 탐색 시간을 줄일 수 있습니다. 또한, start를 stack.pop()으로 수정하여 스택의 마지막 요소를 가져오도록 하여 노드를 방문하게 되었습니다.
4. visited를 set()으로 변경하고, answer를 search 함수 호출 결과로 갱신한 이유는 방문한 노드의 개수를 적절히 카운팅하기 위해서입니다. visited는 중복 방문이 허용되지 않으므로 visited의 길이가 곧 방문한 노드의 개수가 됩니다. search 함수는 방문한 노드의 개수를 반환하므로 이를 answer에 누적하여 최종 결과를 계산할 수 있습니다.