[프로그래머스] 네트워크(BFS,DFS) / C++

euneun·2021년 7월 26일
1

알고리즘

목록 보기
6/12

✅ 프로그래머스 네트워크
문제링크 : https://programmers.co.kr/learn/courses/30/lessons/43162
네트워크의 개수를 return 하도록 solution 함수를 작성하시오.


문제 풀이 방법


네트워크의 개수를 구하는 문제인데,
예제 그림을 잘 살펴보면 결국 연결된 그래프의 개수를 구하는 문제이다.


접근방식

위의 그래프에서 알 수 있듯이, 그래프 문제이고 연결된 그래프의 개수를 구해야 하므로 그래프의 연결된 노드들을 따라서 탐색하다가 연결이 끊기면 네트워크하나가 끝난것이므로 +1해주며 네트워크의 개수를 구하면 된다고 풀이법을 생각해 볼 수 있다.

따라서 깊이 우선 탐색( dfs 관련 참조 )으로 그래프를 탐색해본다.


재귀함수를 작성해보자.

우선, 깊이 우선 탐색을 구현하기 위해 재귀함수를 작성해야한다.

탐색과정을 먼저 말로 풀어보면,

  1. 1번 컴퓨터부터 연결되어있는것들을 탐색해나가는 dfs함수를 호출한다.
  2. 1번 컴퓨터와 연결되어있는것들을 탐색하던 도중에 1번컴퓨터와 2번컴퓨터가 연결되어있는것을 발견한다.
  3. 그 함수내에서 2번컴퓨터의 탐색을 시작해야하므로 2번 컴퓨터를 탐색해나가는 dfs함수를 호출한다.
  4. 2번 컴퓨터와 연결되어있는것들을 탐색하던 도중에 1번컴퓨터와 연결되어있는것을 발견하지만, 이는 1번컴퓨터를 탐색할때 이미 수행한것이다.
    ...

여기서 알 수 있는것은, 각 컴퓨터별로 탐색여부를 체크하는 과정이 필요하다는것이다.
그리고 재귀적으로 dfs함수를 호출할때, 탐색하는 컴퓨터의 번호가 달라지므로 dfs함수의 매개변수로 탐색할 컴퓨터의 번호를 받아야한다는것을 알 수 있다.

문제에서 컴퓨터의 개수는 200개 이하라고 하였으므로, 크기 200인 배열을 선언하여 각 컴퓨터별로 탐색여부를 체크하여 표시한다.

  1. i번째 컴퓨터가 아직 탐색하지 않은 컴퓨터일때 탐색을 시작한다.
    -> dfs(i)호출
  2. i번째 컴퓨터와 연결된 j번째 컴퓨터가 아직 탐색하지 않은 컴퓨터일때 탐색을 시작한다.
    -> dfs(j)호출
  3. j번째 컴퓨터와 연결된 컴퓨터가 없어서 j번째 컴퓨터의 탐색이 종료된다.
    -> dfs(j)종료
  4. dfs(j)를 호출하였던 dfs(i)에서 i번째 컴퓨터의 탐색이 종료된다.
    -> dfs(i)종료

...

이렇게 재귀적으로 호출된 함수가 모두 종료될때가 그래프 한개가 연결된 상태이므로 answer+1을 해준다.


전체 코드

주석 참고해서 이해하시면 좋을 것 같습니다 :)

#include <vector> 
using namespace std; 

int check[200]; 

void dfs(int current_computer, int n, vector< vector<int> > computers) { 
  // current_computer번째 컴퓨터를 체크했다고 표시하기
  check[current_computer] = 1;

  for(int i=0; i<n; i++) { 
    // current_computer와 연결된 컴퓨터들 탐색시작. 
    if(check[i] == 0 && computers[current_computer][i] == 1) {   
      // 다른 컴퓨터와 연결되어 있고, 그 컴퓨터가 아직 탐색하지 않은 컴퓨터라면 탐색 시작
      dfs(i, n, computers); 
    } 
  } 
} 

int solution(int n, vector< vector<int> > computers) { 
  int answer = 0;

  for(int i=0; i<n; i++) { 
    // 아직 검사하지 않은 컴퓨터일때 탐색 시작
    if(check[i] == 0) { 
      dfs(i, n, computers);
      
      // 재귀적으로 호출한 dfs함수가 여기로 돌아올때가 연결된 그래프 하나이므로 answer+1을 해준다.
      answer++; 
    } 
  } 

  return answer;
}


프로그래머스 level3 치고 쉬운 문제였던 것 같다
끝 💫


프로그래머스 bfs/dfs 유형의 다른 문제 풀이법

profile
제대로 짚고 넘어가자!🧐

0개의 댓글