[프로그래머스] 네트워크

1) 문제

프로그래머스의 Level 3 문제 네트워크

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

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

 

연결되어있는 컴퓨터들을 하나의 네트워크라고 보고 computers에서 네트워크의 개수를 return하는 문제이다.

컴퓨터의 최대 개수는 200개이므로 완전탐색으로 풀이 가능할 것으로 보인다.

 

입력 예

	A	B	C
A	1	1	0
B	1	1	0
C	0	0	1

A-B, C 로 네트워크가 총 2개 존재한다.

 

2) 풀이

반복문을 통해 visit하지 않은 computer에 대해 dfs 수행한다.

dfs가 끝나면 answer 가 count된다.

visit 세팅하고

해당 computer에 연결된 다른 computer를 찾고 dfs 수행.

재귀로 반복한다.

 

예

A에서 시작

  visit[A] = 1;

  A에 대해 반복하면서 다음 노드 선택(A-B가 1이므로 다음 노드 B)

    B에 대해 dfs 수행

    visit[B] = 1;

    B에 대해 반복하면서 다음 노드 선택(A는 이미 visit, B-C는 0)

    더이상 연결된 노드 없으므로 return

  return

answer 증가

B는 이미 visit했으므로 pass

...

 

3) 코드

#include <string>
#include <vector>

using namespace std;
int answer = 0;
vector<int> visitArr(200, 0);

void dfs(vector<vector<int>> computers, int i) {
    //i computer 확인했으니 visit 세팅
    visitArr[i] = 1;

    //i computer에 대해 나머지 computer들 확인
    for (int j = 0; j < computers.size(); j++) {
        //이미 확인한 computer가 아니고 연결되어 있는 경우
        if (visitArr[j] == 0 && computers[i][j] == 1) {
            //j computer에 대해 dfs 수행
            dfs(computers, j);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    //각 computer 별로 dfs 수행
    for (int i = 0; i < n; i++) {
        //이미 확인한 computer인가?
        if (visitArr[i] == 0)
        {
            dfs(computers, i);
            //끝까지 수행하면 네트워크 한개 증가
            answer += 1;
        }
    }

    return answer;
}

 

 

4) 정리

dfs의 기본적인 개념을 꼭 생각하자

dfs에 들어온 경우 visit 체크하고 조건에 따라 다음 노드에서 dfs 수행 또는 return

 

오랜만에 알고리즘을 짜려니 매우 헷갈렸다...

간단한 문제인데 결국 다른 풀이를 보고 참고했다 ㅠ

다시 몸에 체득시켜야하는데 걱정이네..