programmers / level3 / 네트워크

[Hwannni]

https://school.programmers.co.kr/tryouts/85938/challenges?language=python3

[Hwannni]

• 이 문제는 기존의 경로 문제들처럼 방문하면 1 증가! 하는 식이 아닌 네트워크가 연결되어 있는 뭉텅이를 구하는 문제
• 그렇다면 메인로직에서 무엇을 파악해야 할까?

def solution(n, computers):
    answer = 0

    # 방문여부 생성 (현재는 모두 False)
    visited = [False] * (n) 

    # 각 노드가 방문했는지에 따라 DFS 함수 호출
    for i in range(n):
        if visited[i] == False:
            answer += 1
            # DFS 함수 호출
            dfs(i)

    # DFS 함수(메인로직)
    def dfs(node):
        # 현재 노드를 기준으로 인접노드 확인
        # 어떻게 해야하지..?

    return answer

[jiminchur]

def dfs(computers,visited,start):
    visited[start] = 1
    for i in range(len(computers)):
        if computers[start][i] == 1 and visited[i] == 0:
            return dfs(computers,visited,i)

def solution(n, computers):
    # 정답에 쓸 변수
    answer = 0
    # 방문한 곳을 찾기 위한 리스트
    visited = [0]*n

    # n으로 for문돌리기
    for start in range(n):
        if visited[start] != 1:
            dfs(computers,visited,start)
            # 빠져나오면 answer에 +1
            answer += 1
    return answer

[jiminchur]

• 3 , [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
• dfs(computers,[0,0,0],0)
• dfs(computers,[1,0,0],1)
• 첫번째로 빠져나옴
• dfs(computers,[1,1,0],2)
• 두번쨰로 빠져나옴