문제
•
사진처럼 컴퓨터가 N개가 있다. (N=3)
•
1번과 2번같이 네트워크가 연결된 컴퓨터는 하나의 네트워크로 본다.
•
컴퓨터의 갯수(int N)과 각 컴퓨터의 연결 상황(int[][] computers)을 받아서 총 몇개의 네트워크가 있는지 구하는 문제.
풀이
•
네트워크가 컴퓨터를 방문함을 나타내는 배열을 만든다.
•
computers 배열을 순회하면서 연결된 컴퓨터에 방문처리를 하고 DFS를 돌린다.
for (int i = 0; i < computers.length; i++) {
if (visited[i] == 0) {
visited = dfs(computers, i, visited);
visited[n]++;
}
}
Java
복사
•
DFS
private int[] dfs(int[][] computers, int i, int[] visited) {
visited[i] = 1;
for (int j = 0; j < computers[i].length; j++)
if (i != j && visited[j] == 0 && computers[i][j] == 1)
dfs(computers, j, visited);
return visited;
}
Java
복사
◦
computers[i][0 ~ i-1]는 컴퓨터와 연결되어 있는 상태를 말한다.
◦
computers[i][i] 같이 자신의 컴퓨터이거나 네트워크에 연결된 상태면 1이다.
더 이상 방문할 곳이 없을 때 까지 DFS를 돌려주면된다.
1.
computers[0] 부터 시작
b.
computer[0][j] 순회
iii.
다시 visited[i] 가 false인 컴퓨터를 찾음.
4.
반복
전체 코드
class Solution {
public int solution(int n, int[][] computers) {
int[] visited = new int[n + 1];
for (int i = 0; i < computers.length; i++) {
if (visited[i] == 0) {
visited = dfs(computers, i, visited);
visited[n]++;
}
}
return visited[n];
}
private int[] dfs(int[][] computers, int i, int[] visited) {
visited[i] = 1;
for (int j = 0; j < computers[i].length; j++)
if (i != j && visited[j] == 0 && computers[i][j] == 1)
dfs(computers, j, visited);
return visited;
}
}
Java
복사