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

바로 다음 문제로 넘어왔습니다!

이번 문제는 이전 문제에 비해 한단계 업그레이드 된 점이 있는데, 바로 방문 여부를 체크하는 것입니다.

원래 DFS는 방문 여부를 체크해서 무한루프를 돌게 하지 않는 것이 맞는데, 전 문제가 이상한겁니다(?)

그렇다면 바로 문제 해설로 넘어가겠습니다.

출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있

programmers.co.kr

0. 문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

0.0. 제한사항

컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
computer[i][i]는 항상 1입니다.

0.1. 입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

0.2. 입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

1. 풀이 과정

문제를 보고 바로 DFS를 생각했습니다. 물론 어짜피 모든 컴퓨터를 확인해야 하기 때문에 BFS로 풀어도 관계 없겠네요.

먼저 global 변수로 chk와 answer를 만들었습니다. global 변수를 많이 쓰는 것은 좋지 않지만, 간혹 이렇게 편리한 상황이 있기 때문에 DFS와 같이 재귀함수를 만드는 경우 자주 쓰게 되는 느낌입니다.

chk변수는 이미 확인한 컴퓨터를 체크하기 위한 변수이고, answer는 네트워크의 수를 나타내기 위한 변수입니다.

chk 변수를 만들었으니 써먹어야겠죠? for문을 이용해 0부터 n까지 chk를 1로 바꿔줍니다. 아직 확인하지 않는 컴퓨터만 1로 체크되어있는 상태가 되겠죠?

그 다음엔 n만큼 다시 for문을 돌려서 아직 확인하지 않은 컴퓨터의 경우 dfs()함수를 돌립니다.

파악하셨을 수도 있지만 조금 더 설명하자면, chk[i] == 1은 확인하지 않은 컴퓨터를 DFS돌리겠다는 뜻이고, 이 DFS를 돌리게 되면 i번째 위치한 컴퓨터와 연결된 모든 컴퓨터들을 확인할 수 있게 DFS함수를 만들어야 한다는 것을 유추할 수 있습니다.

이제 solution함수 위쪽에 DFS함수를 만들어줍시다.

DFS 함수의 파라미터로 사용할 vector<vector<int>>는 변경하지 않을 것이기 떄문에 call by reference로 불러와서 복사하지 않고 사용했습니다. 그리고 어떤 컴퓨터를 확인하고 있는지를 알려주는 idx변수를 받아주었죠.,

DFS 내부코드를 짜기 위해서는 먼저 chk[idx]가 1인지를 확인해야 합니다. solution함수에서 한번 걸렀지만, DFS 내부에서 발생하는 재귀함수는 걸러내지 못하기 때문이죠.

만약 아직 확인하지 않은 컴퓨터라면(chk[idx] == 1) 확인했다는 의미로 chk[idx]를 0으로 바꿔주고 computers[idx]에서 1인 친구들을 다시 DFS 함수로 돌려줍니다. 이렇게 만들면 이미 확인한 컴퓨터는 chk[idx]가 0이기 때문에 더 돌아가지 않겠죠.

이 과정을 거치면 한 컴퓨터에 연결된 모든 컴퓨터들의 chk가 0이 됩니다. 그리고 ++answer를 통해 네트워크의 개수를 1개 늘려줍니다.

여기서 0이 아닌 친구들이 남아있다면 아까 solution함수에서 만들어준 for문 안에 있는 조건인 chk[i] == 1에서 걸려서 다시 새로운 DFS가 돌게 됩니다. 결국 1로 만들어준 모든 chk가 0이 될 때까지 돌아가게 되겠죠. 그리고 solution 내에 있는 DFS가 돌아간 만큼 answer도 증가하여 네트워크의 총 개수를 알려줄 것입니다.

2. 소스 코드

#include <string>
#include <vector>
#include <stack>
using namespace std;

// 경로체크
int chk[200] = {0,};
int answer = 0;

void dfs(vector<vector<int>>& v, int idx){
    if(chk[idx] == 1){
        chk[idx] = 0;
        for (int i = 0; i < v[idx].size(); ++i){
            if(v[idx][i] == 1){
                dfs(v, i);
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    // dfs인데, 경로를 체크해야한다
    // 존재하는 컴퓨터에다가 1을 부여, 한 네트워크에 컴퓨터가 포함되면 0으로 처리
    for (int i = 0; i < n; ++i)
        chk[i] = 1;
    
    // 네트워크에 포함되지 않은 컴퓨터의 경우 dfs를 돌림
    for (int i = 0; i < n; ++i){
        if(chk[i] == 1){
            dfs(computers, i);
            ++answer;
        }
    }
    
    return answer;
}