✅ 프로그래머스 네트워크
문제링크 : https://programmers.co.kr/learn/courses/30/lessons/43162
네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
문제 풀이 방법
네트워크의 개수를 구하는 문제인데,
예제 그림을 잘 살펴보면 결국 연결된 그래프의 개수를 구하는 문제이다.
접근방식
위의 그래프에서 알 수 있듯이, 그래프 문제이고 연결된 그래프의 개수를 구해야 하므로 그래프의 연결된 노드들을 따라서 탐색하다가 연결이 끊기면 네트워크하나가 끝난것이므로 +1해주며 네트워크의 개수를 구하면 된다고 풀이법을 생각해 볼 수 있다.
따라서 깊이 우선 탐색( dfs 관련 참조 )으로 그래프를 탐색해본다.
재귀함수를 작성해보자.
우선, 깊이 우선 탐색을 구현하기 위해 재귀함수를 작성해야한다.
탐색과정을 먼저 말로 풀어보면,
- 1번 컴퓨터부터 연결되어있는것들을 탐색해나가는 dfs함수를 호출한다.
- 1번 컴퓨터와 연결되어있는것들을 탐색하던 도중에 1번컴퓨터와 2번컴퓨터가 연결되어있는것을 발견한다.
- 그 함수내에서 2번컴퓨터의 탐색을 시작해야하므로 2번 컴퓨터를 탐색해나가는 dfs함수를 호출한다.
- 2번 컴퓨터와 연결되어있는것들을 탐색하던 도중에 1번컴퓨터와 연결되어있는것을 발견하지만, 이는 1번컴퓨터를 탐색할때 이미 수행한것이다.
...
여기서 알 수 있는것은, 각 컴퓨터별로 탐색여부를 체크하는 과정이 필요하다는것이다.
그리고 재귀적으로 dfs함수를 호출할때, 탐색하는 컴퓨터의 번호가 달라지므로 dfs함수의 매개변수로 탐색할 컴퓨터의 번호를 받아야한다는것을 알 수 있다.
문제에서 컴퓨터의 개수는 200개 이하라고 하였으므로, 크기 200인 배열을 선언하여 각 컴퓨터별로 탐색여부를 체크하여 표시한다.
i번째 컴퓨터가 아직 탐색하지 않은 컴퓨터일때 탐색을 시작한다.
->dfs(i)호출i번째 컴퓨터와 연결된j번째 컴퓨터가 아직 탐색하지 않은 컴퓨터일때 탐색을 시작한다.
->dfs(j)호출j번째 컴퓨터와 연결된 컴퓨터가 없어서j번째 컴퓨터의 탐색이 종료된다.
->dfs(j)종료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 유형의 다른 문제 풀이법
