오늘 문제는 프로그래머스에 있는 네트워크라는 문제를 풀었다.
문제의 설명은 다음과 같다.
문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
이 문제를 보고 생각을 했다.
"컴퓨터 한개를 선택해서 연결 되어 있는 컴퓨터를 이어서 따라가서 끝에 도달하면 그것을 네트워크 한개로 정하면 되지 않을까?"
이 문제 해결에 필요한 알고리즘을 생각해 보았을 때 dfs를 사용하여 풀 수 있을 거라고 생각이 들었다.
그래서 다음과 같이 풀이를 하였다.
class Solution {
int[][] computers;
boolean[] visit;
public int solution(int n, int[][] computers) {
int answer = 0;
this.computers = computers;
visit = new boolean[computers.length];
for (int i = 0; i < computers.length; i++) {
if (!visit[i]) {
visit[i] = true;
dfs(i, computers[i]);
answer++;
}
}
return answer;
}
public void dfs(int index, int[] connectNodes) {
for (int i = 0; i < connectNodes.length; i++) {
if (i != index && connectNodes[i] == 1 && !visit[i]) {
visit[i] = true;
dfs(i, computers[i]);
}
}
}
}우선 컴퓨터들과 방문처리를 위한 변수를 전역으로 두고 컴퓨터 수만큼 boolean배열을 만들었다.
그리고 컴퓨터 수만큼 반복문을 돌려 방문처리가 안되어 있다면 방문처리 후 dfs 함수에 넣어서 연결되어 있는 모든 컴퓨터를 방문하고 연결되어 있는 모든 컴퓨터들 방문이 끝이 났을 때 네트워크 수를 한개 증가시켜주었다.
dfs 함수에서는 현재 컴퓨터의 위치 인덱스를 받고 연결되어 있는 컴퓨터들의 정보 배열을 넘겨주는 형태로 만들었다.
내부에서는 자신의 위치를 제외하고 컴퓨터의 정보가 1일 때 연결이 되어 있는 것이기 때문에 1이고 방문이 안 되어 있을 때 방문처리 후 dfs 함수에 다시 넣어주는 형식으로 돌아가게 구현하였다.
이 코드가 돌아가게 되면 연결되어 있는 컴퓨터들이 하나의 네트워크로 판별되고 최종 네트워크 수를 구할 수 있게 된다.
DFS(Depth-First Search)란
- 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
- 시작 노드를 방문하고 연결된 다음 노드에 방문, 그 다음 연결된 노드에 방문 이렇게 반복하는 구조이다.
- 그러다 연결이 되어있지 않거나, 모두 방문한 노드라면 이전 노드로 이동 후 연결된 노드(방문이 안된 노드)에 대해 다시 DFS를 수행한다.
