bfs (1) 썸네일형 리스트형 [알고리즘] 프로그래머스 - 네트워크 DFS를 풀었다면, 당연히 BFS도 풀어주는게 알고리즘의 도리이다. 이번에 볼 내용은 프로그래머스의 네트워크이다. 문제를 먼저 보겠다. 문제 문제설명 2차원 배열로 주어진 computers에서 서로 연결된 네트워크의 개수를 구하는 것이다. 이때 제한사항 중에서 아래와 같은 사항을 알 수 있다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현한다는 것은, 모든 배열을 다 탐색할 필요가 없고, n^2 / 2 + n 만큼 탐색을 진행하면 된다. O(n^2)로 O(n^2/2)로 시간 복잡도를 줄일 수 있다. 노드 1개 자체만으로도 네트워크가 될 수 있다. 접근방법 BFS로 진행했다. 이때 1노드와 2노드가 연결되었다고 할 때 탐색을할 때 1노드에서만 진행하고 2노드는 따로 .. 이전 1 다음
