문제 파악
네트워크
컴퓨터 A와 컴퓨터 B는 직접적으로 연결되어 있다.
컴퓨터 B와 컴퓨터 C는 직접적으로 연결되어 있다.
→ 컴퓨터 A와 C는 간접적으로 연결되어 있다.
A-B
B-C
A-C
A-B-C
이를 하나의 네트워크라고 한다.
매개변수로 컴퓨터의 개수 n 컴퓨터의 연결 정보가 담긴 2차원 배열 computers가 주어질 때, 네트워크의 개수를 return하라.
제한 사항
- 컴퓨터의 개수 n은 1 이상 200 이하인 자연수이다.
- 각 컴퓨터는 0부터
n-1인 정수로 표현한다. - i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현한다.
- computers[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 | A | B | C |
|---|---|---|---|
| A | 1 | 1 | 0 |
| B | 1 | 1 | 0 |
| C | 0 | 0 | 1 |
A-B
B-A
C
위처럼 A와 B는 서로 연결되어 있지만, C는 다른 컴퓨터와 연결되어 있지 않다.
따라서 네트워크의 개수는 2이다.
| 입력 예제 2 | A | B | C |
|---|---|---|---|
| A | 1 | 1 | 0 |
| B | 1 | 1 | 1 |
| C | 0 | 1 | 1 |
A-B
B-A
B-C
C-B
A-B-C
위처럼 3대의 컴퓨터는 서로 연결되어 있다.
따라서 네트워크의 개수는 1이다.
네트워크는 그래프로 표현할 수 있다.
모든 네트워크를 탐색하고 한 개의 네트워크가 탐색이 끝나면 count하면 된다.
그래프 탐색에는 BFS와 DFS가 있다.
단순히 탐색만 하는 문제라 둘 중에 어느 것을 사용해도 되므로, BFS와 DFS 둘 다 익숙해지기 위해 두 방법으로 코드를 작성해보겠다.
BFS사용
먼저 BFS로 그래프를 탐색하는 것부터 구현해보자.
2차원 배열 computers[i][j]의 [0][0]부터 차례대로 Queue에 넣어보자.
이 때, i == j 인 경우는 건너 뛴다. → i와 j가 같은 경우는 자기 자신을 가리키기 때문이다.
Queue에 [0][1]을 넣고 방문 표시를 한다.
[1][0]부터 값이 1인 인덱스를 탐색한다. → 1이면 이어지고, 0이면 이어지지 않는다.
탐색한 인덱스가 1이면 해당 인덱스의 방문 여부를 확인한다.
방문했으면 다음으로 넘어가고 그렇지 않으면 Queue에 삽입한다.
더 방문할 인덱스가 없으면 탐색을 종료한다.
위 과정을 코드로 작성해보자.
import java.util.Queue;
import java.util.HashMap;
Queue<Integer> queue = new Queue<>();
HashMap<Integer, Boolean> visited = new HashMap<>();
int answer = 0;
for(int i = 0; i < computers.length; i++) {
bfs(0, true);
}
public void bfs(int node, boolean visit) {
queue.push(node);
visited.put(0, true);
while(!queue.isEmpty()) {
node = queue.poll();
for(int i = 0; i < computers[node].length; i++) {
if(node == i) {
continue;
} else if(computers[node][i] == 1 && visited.get(i) != true) {
queue.push(i);
visited.put(i, true);
}
}
}
answer++;
}이제 프로그래머스에 옮겨 적어보자.
import java.util.Queue;
import java.util.LinkedList;
class Solution {
public void bfs(int node, int[][] computers, boolean[] visited) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(node);
visited[node] = true;
while(!queue.isEmpty()) {
node = queue.poll();
for(int i = 0; i < computers[node].length; i++) {
if(node == i) {
continue;
} else if(computers[node][i] == 1 && visited[i] != true) {
queue.offer(i);
visited[i] = true;
}
}
}
}
public int solution(int n, int[][] computers) {
boolean[] visited = new boolean[n];
int answer = 0;
for(int i = 0; i < computers.length; i++) {
if(visited[i] == false) {
answer++;
bfs(i, computers, visited);
}
}
return answer;
}
}정답!
DFS 사용
BFS를 사용해서 해결했으니, 이번엔 DFS로 풀어보자.
DFS는 재귀 호출을 사용해야 한다.
시작 노드를 DFS 함수의 매개변수로 넣어준다.
시작 노드를 받은 DFS 함수는 방문 여부를 표시하고, 시작 노드가 어디와 연결되어 있는지 배열을 탐색한다.
BFS와 마찬가지로 i == j 인 경우는 건너 뛴다. → i와 j가 같은 경우는 자기 자신을 가리키기 때문이다.
computer[node][i]가 1이면, 다시 DFS 함수에 매개변수로 i값을 넣어준다.
그러면 재귀 호출로 인해 DFS를 반복하여 그래프를 탐색할 수 있다.
위 과정을 코드로 작성해 보자.
public void dfs(int currentNode, int[][] computers, boolean[] visited) {
visited[currentNode] = true;
for(int i = 0; i < computers[currentNode].length; i++) {
if(computers[currentNode][i] == 1 && !visited[i]) {
dfs(i, computers, visited);
}
}
}아래는 프로그래머스에 위 코드를 옮겨 적은 것이다.
import java.util.Queue;
import java.util.LinkedList;
class Solution {
public void dfs(int currentNode, int[][] computers, boolean[] visited) {
visited[currentNode] = true;
for(int i = 0; i < computers[currentNode].length; i++) {
if(computers[currentNode][i] == 1 && !visited[i]) {
dfs(i, computers, visited);
}
}
}
public int solution(int n, int[][] computers) {
boolean[] visited = new boolean[n];
int answer = 0;
for(int i = 0; i < n; i++) {
if(!visited[i]) {
answer++;
dfs(i, computers, visited);
}
}
return answer;
}
}정답!
코드 구현
import java.util.Queue;
import java.util.LinkedList;
class Solution {
public void bfs(int node, int[][] computers, boolean[] visited) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(node);
visited[node] = true;
while(!queue.isEmpty()) {
node = queue.poll();
for(int i = 0; i < computers[node].length; i++) {
if(node == i) {
continue;
} else if(computers[node][i] == 1 && visited[i] != true) {
queue.offer(i);
visited[i] = true;
}
}
}
}
public int solution(int n, int[][] computers) {
boolean[] visited = new boolean[n];
int answer = 0;
for(int i = 0; i < computers.length; i++) {
if(visited[i] == false) {
answer++;
}
bfs(i, computers, visited);
}
return answer;
}
}배우게 된 점
처음으로 BFS를 직접 구현해 보았다.
답안을 보지 않고 했더니, BFS만 구현하는데 2시간이나 걸렸다.
익숙해지도록 연습을 많이 해야겠다.
DFS는 생각보다 훨씬 빠르게 구현했다. 10분 정도 걸린 것 같다.
DFS가 BFS보다 구현하기 쉬운 걸까?
