Problem Solving/백준

[백준] 11724. 연결 요소의 개수 (+파이썬 코드)

sohyunwriter 2021. 2. 15. 02:41

Question. 백준 11724. 연결 요소의 개수

 

 

 


Answer.

 

프로그래머스의 "네트워크"랑 비슷한 문제여서 자세한 풀이는 생략한다.

sohyunwriter.tistory.com/90

 

[프로그래머스] "네트워크" (+파이썬 코드)

Question. 프로그래머스 깊이/너비 우선 탐색(DFS/BFS) > 네트워크 Answer. computers라는 인접행렬(adjacency matrix) graph가 주어지는데, 해당 graph에서 connected component가 몇 개인지 구하는 문제이다. b..

sohyunwriter.tistory.com

 

sol 1) 인접리스트 + dfs 반복문

 

주의사항

1) sys.stdin.readline 써야 시간초과 안 남

2) dfs 돌릴 때, visited한 node는 continue 해야 시간초과 안 남

 

import sys
input = sys.stdin.readline

def count_connected_component(n, graph):
    cnt = 0
    visited = [False] * (n+1)

    def dfs(graph, visited, start):
        stack = [start]
        while stack:
            j = stack.pop()
            if visited[j]:
                continue

            visited[j] = True

            for i in graph[j]:
                if not visited[i]:
                    stack.append(i)

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

if __name__ == "__main__":
    n, m = map(int, input().split())

    # make graph
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    # count connected component
    answer = count_connected_component(n, graph)

    print(answer)

 

 

sol 1) 
Time Complexity O(V+E)
Space Complexity O(V+E)
728x90