냄비
문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
제한사항
- 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
- 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
- i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers [i][j]를 1로 표현합니다.
- computer [i][i]는 항상 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 |
입출력 예 설명
예제 #1
아래와 같이 2개의 네트워크가 있습니다.
예제 #2
아래와 같이 1개의 네트워크가 있습니다.
구현
computers 배열을 새로운 vector에 저장 후 해당 vector를 DFS로 탐색하며 탐색하러 들어간 computer에 대하여 해당 computer의 부모 노드를 탐색하러 가기 전의 computer의 부모로 바꾸어준다.
모든 computer에 대하여 탐색이 마치고 난다면 parent vector는 각자 최상위 노드를 가진 vector로 바뀔것이며 해당 vector의 값이 다른 것만 찾으면 network의 개수가 완성이 된다.
천천히 예를 보며 알아보자.
<0>
| parent | ||
| 0 | 1 | 2 |
| 0 | 1 | 2 |
| networks | |
| n | vector |
| 0 | 1 |
| 1 | 0 |
| 2 | - |
최초에 위와 같이 구성을 한다.
<1>
첫 번째 탐색은 0번부터 시작하여 0->1
| parent | ||
| 0 | 1 | 2 |
| 0 | 0 | 2 |
| networks | |
| n | vector |
| 0 | - |
| 1 | 0 |
| 2 | - |
<2>
두 번째 탐색은 1->0
| parent | ||
| 0 | 1 | 2 |
| 0 | 0 | 2 |
| networks | |
| n | vector |
| 0 | - |
| 1 | - |
| 2 | - |
위의 과정을 거치면 parent vector는 각 노드의 최상단 부모노드를 가리키게 되고 결국 한 개의 네트워크를 이루게 되므로 2개의 네트워크가 나오게 된다.
다만 해당 문제에서 가장 잘 봐야할 점은 입력으로 주어지는 computers가 항상 대칭적으로 주어지지 않는다는 점이다.
(문제에서는 대칭적인 것 처럼 해놓고.. 30분을 더 잡아먹었다.)
따라서 computers 배열을 새로운 network vector로 옮길 때 주의해야 한다.
나머지 설명은 코드에 덧붙이겠다.
전체 코드는 아래에서 볼 수 있다.
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
vector<int> networks[201];
vector<int> parent;
void dfs(int num)
{
//networks에 저장된 간선들의 도착점에 대하여 탐색한다.
for (int i = 0; i < networks[num].size();)
{
//tmp에 저장해주는 이유는 간선을 탐색하러가기전에 해당 간선을 삭제해주는 방식으로 사용할 것이기 때문이다.
int tmp = networks[num][i];
//도착할 간선의 부모를 출발할 간선의 부모로 바꿔준 후
parent[networks[num][i]] = parent[num];
//해당 간선을 삭제해준 후
networks[num].erase(networks[num].begin());
//다음 간선으로 넘어간다.
dfs(tmp);
}
}
int solution(int n, vector<vector<int>> computers)
{
int answer = 1;
for (int i = 0; i < n; i++)
parent.push_back(i);
for (int i = 0; i < computers.size(); i++)
{
for (int j = 0; j < computers[i].size(); j++)
{
//간선이 연결되어 있고 내 자신이 아니라면
if (computers[i][j] == 1 && i != j)
{
//대칭적이지 않다면 양쪽 다 추가해주고
if (computers[j][i] == 0)
{
networks[i].push_back(j);
networks[j].push_back(i);
}
//대칭적이라면 한쪽만 추가해준다.
else
networks[i].push_back(j);
}
}
}
//dfs 과정
//i가 0에서 n까지 모두 도는 이유는 0번이 단독인 network일 수가 있기에 모든 i에 대하여 수행해야한다.
for (int i = 0; i < n; i++)
{
if (!networks[i].empty())
dfs(i);
}
// 답 도출
sort(parent.begin(), parent.end());
int tmp = parent[0];
for (int i = 0; i < parent.size(); i++)
{
if (parent[i] != tmp)
{
tmp = parent[i];
answer++;
}
}
return answer;
}1가지 예시를 더 들어보겠다.
int n = 5;
vector<vector<int>> c = {{1, 0, 0, 0, 0}, {0, 1, 0, 0, 1}, {0, 0, 1, 0, 1}, {0, 0, 0, 1, 1}, {1, 0, 0, 0, 1}};
위와 같은 간선의 구조가 주어졌을 경우 양쪽 모두 저장해주지 않는다면
| 0 | - |
| 1 | 4 |
| 2 | 4 |
| 3 | 4 |
| 4 | 0 |
와 같은 형태를 띠게 된다.
이렇게 될 경우 최종적으로 parent vector는
| 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 3 |
와 같은 형태를 띄게 된다.
- 0-> x
- 1->4 (4번의 부모는 1)
- 4->0 (0번의 부모는 1)
- 2->4 (4번의 부모는 2)
- 3->4 (4번의 부모는 3)
만약 두 가지 모두 vector에 추가를 해준다면
| 0 | 4 |
| 1 | 4 |
| 2 | 4 |
| 3 | 4 |
| 4 | 1,2,3,0 |
이고
최종적으로 parent vector는
| 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 |
이 되어서 답을 도출해낼 수 있게 된다.
- 0->4 (4번의 부모는 0)
- 4->1 (1번의 부모는 0)
- 1->4->2 (2번의 부모는 0)
- 2->4->3 (3번의 부모는 0)
- 3->4->0 (완료)
댓글