이번에 푼 문제는 프로그래머스의 네트워크 문제이다.
문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.
입출력 Ex
| 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개
이 문제는 undirect graph를 이용한 그래프 탐색 알고리즘 문제이다.
먼저 예제를 분석하면서 문제의 요구사항에 대해 설명하겠다.
EX 1: computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
INPUT으로 인접행렬인 computers가 주어지고 있다.
- 인접행렬 인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식이다.
인접 행렬을 adj[][]라고 한다면 adj[i][j]에 대해서 다음과 같이 정의할 수 있다.
adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0
각 컴퓨터가 어떤 컴퓨터랑 연결되어 있는지 보자.
computers를 보면 1와 2는 서로 연결되어 있으나, 3은 어떤 컴퓨터와도 연결되어 있지 않다.
즉, 노드 1과 2는 위 사진처럼 간선 연결되나 C는 어느 노드와도 연결되지 않는다.
따라서 네트워크는 아래의 2개이다.
- 노드 1-2 네트워크
- 노드 3 네트워크
EX 2: computers = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]
computers를 보면 1와 2는 서로 연결되어 있고, 2는 3과 연결되어 있다.
즉, 노드 1과 2가 간선 연결, 2와 3이 간선 연결된다.
간접적으로 연결된 노드도 같은 네트워크 상에 있다고 보므로 네트워크는 1개이다.
- 노드 1-2-3 네트워크
DFS로 푼 이유
문제는 각 노드에서 자신이랑 인접한 노드를 "모두" 찾는게 목표이므로, DFS/BFS 둘 다로 풀 수 있다.하지만 나는 DFS로 풀었는데, 그 이유에 대해 설명하겠다.
예제 #2를 보면 “간접적으로 연결”된 컴퓨터도 동일 네트워크에 있다고 본다.
즉 노드 A에서 “연결되지 않은 노드 B”가 있더라도, A와 연결된 노드 중 B와 연결된 노드가 있다면 “동일 네트워크”라는 것이다.
따라서 !
- A에서 연결되지 않은 노드가 있다면 이전에 방문한 노드(B)로 돌아간 다음,
- 나머지 노드들 중 연결된 노드가 있는지 탐색해야 한다.
- 이 때 A에서 연결되지 않은 노드가 B에서 연결된다면 동일 네트워크다.
이러한 알고리즘은 DFS이다.
예제
예제로 설명하겠다. computers= [[1,1,1], [1,1,0], [1,0,1]]로 주어졌다고 가정하자.
- 모든 노드를 “방문 안 함” 표시한다. 방문 안 한 노드를 기준으로 탐색을 시작한다.
- 노드 A에서 탐색을 시작한다. A를 방문함 표시를 한다.
노드 A는 B와 인접한다. 따라서 노드 B로 가서 방문함 표시를 한다음, B와 인접한 노드를 찾는다. - 노드 B는 방문하지 않은 노드(C) 중 인접한 노드가 없다.
따라서 다시 직전에 방문한 노드인 A로 돌아간다. - 노드 A에서 방문하지 않은 노드(C) 중 인접한 노드로 C가 있다.
따라서 노드 C로 가서 방문함 표시를 한다. - 이처럼 노드A, B, C는 서로 연결되어 있으므로 같은 네트워크이다.
Pseudocode
answer = 0
모든 노드를 방문 안함 표시
function DFS(v) {
for (w가 v에 인접) and (w가 방문 안 함) then
DFS(w)
}
for(모든 노드) {
if (방문 안 한 노드 z) {
DFS(z)
answer += 1
}
}전체 코드
function solution(n, computers) {
let network = 0;
const visit = new Array(n).fill(false);
function DFS(v) {
visit[v] = true;
for (let w = 0; w < computers.length; w++) {
if ((computers[v][w] === 1) && (!visit[w])) {
DFS(w);
}
}
}
for(let w = 0; w < n; w++) {
if (!visit[w]) {
network += 1;
DFS(w);
}
}
return network;
}