참고
문제해설
문제 로직고민
NOTE
•
그래프의 모든 정점을 DFS로 탐색하는데 필요한 횟수를 판단하면 된다.
◦
방문하지 않은 정점은 DFS로 탐색을한다.
◦
탐색이 가능한 모든 정점을 방문하고, 방문하지 않은 정점이 있는지 확인하고 반복한다.
작성코드
NOTE
class Solution {
int n;
int[][] computers;
boolean[] visited;
public int solution(int n, int[][] computers) {
this.n = n;
this.computers = computers;
this.visited = new boolean[n];
int answer = 0;
for(int i=0; i<n; i++){
if(!visited[i]){
answer++;
dfs(i);
}
}
return answer;
}
private void dfs(int vertex){
visited[vertex] = true;
for(int i=0; i<n; i++){
if(!visited[i] && computers[vertex][i] == 1){
dfs(i);
}
}
}
}
Java
복사
다른사람 풀이
NOTE
class Solution {
public int solution(int n, int[][] computers) {
int answer = 0;
boolean[] chk = new boolean[n];
for(int i = 0; i < n; i++) {
if(!chk[i]) {
dfs(computers, chk, i);
answer++;
}
}
return answer;
}
void dfs(int[][] computers, boolean[] chk, int start) {
chk[start] = true;
for(int i = 0; i < computers.length; i++) {
if(computers[start][i] == 1 && !chk[i]) {
dfs(computers, chk, i);
}
}
}
}
Java
복사
쉬운문제라 크게 참고할게 없다.