-
프로그래머스 - 네트워크알고리즘 풀이/프로그래머스 2019. 11. 13. 20:57
문제 : https://programmers.co.kr/learn/courses/30/lessons/43162
코딩테스트 연습 - 네트워크 | 프로그래머스
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크
programmers.co.kr
풀이 :
기본 DFS문제로 DFS를 통해 연결돼있는 컴포넌트가 몇 개 인지 찾는 문제였다.
코드(C++)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters#include <string> #include <vector> #include <iostream> #include <set> #include <algorithm> #include <queue> using namespace std; bool visited[201]; int n, m; void DFS(int x, vector<vector<int>>& computers) { for (int i = 0; i < m; ++i) { if (visited[i]) continue; if (computers[x][i] == 1) { visited[i] = true; DFS(i, computers); } } } int solution(int n, vector<vector<int>> computers) { int answer = 0; n = computers.size(); m = computers[0].size(); for (int i = 0; i < n; ++i) { if (visited[i]) continue; DFS(i, computers); answer++; } return answer; } '알고리즘 풀이 > 프로그래머스' 카테고리의 다른 글
프로그래머스 - 프린터 (0) 2019.12.01 프로그래머스 - 전화번호 목록 (0) 2019.11.21 프로그래머스 - 소수 찾기 (0) 2019.11.13 프로그래머스 - 더 맵게 (0) 2019.11.13 프로그래머스 - K번째수 (0) 2019.11.07