문제
접근법
결국 그래프를 탐색하는 문제이기 때문에 DFS, BFS 둘중 하나를 선택해서 사용하면 되는 생각보다 쉬운 문제이다.
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); //컴퓨터 수
int M = Integer.parseInt(br.readLine()); //네트워크 상에서 연결되어 있는 컴퓨터 쌍의 수
List<List<Integer>> graph = new ArrayList<>(N);
for (int i = 0; i < N+1; i++) {
graph.add(new ArrayList<>());
}
boolean[] BFS_visited = new boolean[N+1];
boolean[] DFS_visited = new boolean[N+1];
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int e = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
graph.get(e).add(v);
graph.get(v).add(e);
}
int count = 0;
// count = findByDFS(graph, BFS_visited, count, 1);
count = findByBFS(graph, DFS_visited);
System.out.println(count);
}
private static int findByDFS(List<List<Integer>> graph, boolean[] visited, int count, int start) {
visited[start] = true;
List<Integer> E = graph.get(start);
for (int i : E) {
if (!visited[i]) {
count = findByDFS(graph, visited, count, i);
count++;
}
}
return count;
}
private static int findByBFS(List<List<Integer>> graph, boolean[] visited) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
visited[1] = true;
int count = 0;
while (!queue.isEmpty()) {
Integer i = queue.poll();
List<Integer> E = graph.get(i);
for (int j : E) {
if (!visited[j]) {
queue.offer(j);
visited[j] = true;
count++;
}
}
}
return count;
}
}실행 결과
같은 문제조건에서 DFS와 BFS 중 어떤 코드가 더 빠를까?
DFS
BFS
⇒ 아주 근소한 차이지만 BFS가 조금더 빠른 것을 알 수 있었다!
시간차이가 나는 이유는 무엇일까?
- DFS : 재귀호출을 사용하기 때문에 함수 호출 스택의 관리와 함수 진입 및 반환의 오버헤드가 발생한다.
- BFS : 반복문과 큐를 사용하며, 호출 스택을 관리할 필요가 없으므로 오버헤드가 발생하지 않는다.
→ 따라서 그래프의 연결성(즉, 간선의 개수에 비해 정점의 개수)이 높을수록 BFS가 더 효율적으로 작동한다. 반면, 연결성이 낮으면 DFS도 비슷한 성능을 낼 수 있다.
시간복잡도
두 코드의 시간복잡도는 모두 O(V + E) 이다.
- V : 정점의 수
- E : 간선의 수
→ 따라서 두 알고리즘의 이론적인 실행시간은 동일하다. 하지만 실제 실행 시간에는 오버헤드로 인해 위에서 설명한 요인들이 영향을 준다.
트러블슈팅
이슈 1
- 문제
- 재귀함수에서 count를 어떻게 return 해줘야 할까?
private static int findByDFS(List<List<Integer>> graph, boolean[] visited, int count, int start) {
visited[start] = true;
List<Integer> E = graph.get(start);
count++;
for (int i : E) {
if (visited[i] != true) {
findByDFS(graph, visited, count, i);
}
}
return count;
}이렇게 하면 count가 변하지 않는다.
- 원인
- 재귀함수를 호출하면서 마지막 count가 return되어버림
7
6
1 2
2 3
1 5
5 2
5 6
4 7
> Task :Main.main()
2
3
2
1
1
=> 이렇게 제일 마지막에 return 되는 count가 1이 될수밖에 없는 구조- 해결
- 재귀호출되는 수를 세어주면 되지 않을까?
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); //컴퓨터 수
int M = Integer.parseInt(br.readLine()); //네트워크 상에서 연결되어 있는 컴퓨터 쌍의 수
List<List<Integer>> graph = new ArrayList<>(N);
for (int i = 0; i < N+1; i++) {
graph.add(new ArrayList<>());
}
boolean[] BFS_visited = new boolean[N+1];
boolean[] DFS_visited = new boolean[N+1];
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int e = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
graph.get(e).add(v);
graph.get(v).add(e);
}
int count = 0;
count = findByDFS(graph, BFS_visited, count, 1);
System.out.println(count);
// int count = findByBFS(graph, DFS_visited);
}
private static int findByDFS(List<List<Integer>> graph, boolean[] visited, int count, int start) {
visited[start] = true;
List<Integer> E = graph.get(start);
for (int i : E) {
if (!visited[i]) {
count = findByDFS(graph, visited, count, i);
count++;
}
}
return count;
}
private static int findByBFS(List<List<Integer>> graph, boolean[] dfsVisited) {
return 0;
}
}해결완료!