[프로그래머스/Python] DFS/BFS - 네트워크

비슷한 문제
[백준/Python] DFS/BFS - 11724번 연결 요소의 개수

🤓 나의 풀이

def dfs(graph,v,visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)
            
def solution(n, computers):
    answer = 0
    graph = [[] for _ in range(n)]
    visited = [False] * n
    
    # graph = [[1], [0], []]
    # graph = [[1], [0, 2], [1]]
    for i in range(n):
        for j in range(n):
            if computers[i][j] == computers[j][i] == 1:
                if i != j:
                    graph[i].append(j)
    for i in range(n):
        if visited[i] == False:
            dfs(graph,i,visited)
            answer += 1
    return answer

수정 (2021.06.13)

해결 과정

• DFS함수를 먼저 작성
• 탐색 돌아야하는 그래프 만들기

시행착오

• DFS함수 좀 완벽하게 외우자
• 그래프 만드는데 좀 헷갈렸음

풀이

# DFS 구현
def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)
        
def solution(n, computers):
    answer = 0
    graph = [[] for _ in range(n+1)]
    visited = [False] * (n+1)
    
    # graph = [[], [2], [1], []]
    # graph = [[], [2], [1, 3], [2]]
    for i in range(len(computers)):
        for j in range(n):
            if i == j:
                continue
            if computers[i][j] == 1:
                    graph[i+1].append(j+1)

    for i in range(1,len(graph)):
        if not visited[i]:
            dfs(graph,i,visited)
            answer += 1
    return answer