알고리즘(c++) / 프로그래머스 level 3 : 네트워크

알고리즘(c++) / 프로그래머스 level 3 : 네트워크

level 3 : 네트워크

https://programmers.co.kr/learn/courses/30/lessons/43162

코드

//프로그래머스 네트워크 #include #include #include using namespace std; vector> computers_copy; bool visited[201] = { false, }; void DFS(int node) { visited[node] = true; //방문한 노드 for (int i = 0; i < computers_copy.size(); i++) { if (visited[i] == false) { if (computers_copy[node][i] == 1) { DFS(i); } } } } int solution(int n, vector> computers) { int answer = 0; computers_copy = computers; //전역변수 for (int i = 0; i < n; i++) { if (visited[i] == false) { DFS(i); answer++; } } return answer; } int main() { int n = 3; vector> computers = { {1,1,0}, {1,1,1}, {0,1,1} }; cout << solution(n, computers) << "

"; return 0; }

설명

computers를 computers_copy로 전역 변수 선언하였다. DFS에서 참조형 변수(&)로 선언할 수 있지만 전역변수로 선언하여 더 편하게 구현할 수 있다. 노드의 방문을 확인하는 visited도 마찬가지로 전역변수로 선언해주었다.

방문되지 않은 노드 중 이동할 수 있는 노드인지를 판단하여 이동하게 된다.(DFS)

고찰

백준에서도 DFS/BFS 문제를 많이 풀어봐서 쉽게 구현할 수 있었던거 같다.

from http://se-jung-h.tistory.com/126 by ccl(A) rewrite - 2021-08-02 16:00:18